yjq_1999

记f[i] = 第i个fibonacci数，f[0] = f[1] =1;
观察可得Vi·Vj = f[(i+j)*2-1]

求出前n<<2个fibonacci数计算贡献即可

复杂度O(N)

代码：
#include <cstdio>
#include <algorithm>

using namespace std;
int C,M,n;
int cnt = 0;
int ans[2000010],tp = 0;
int main() {
#ifdef YJQ_LOCAL
  freopen(".in","r",stdin);
  freopen(".out","w",stdout);
#endif
  scanf("%d%d%d",&C,&M,&n);
  int f0 = 1,f1 = 1;
  if (n == 1) {
    puts("0");return 0;
  }
  for (int i = 2;i <= (2 * n - 1) * 2;i ++) {
      int g = (f0 + f1);
      if (g >= M) g -= M;
      if ((!(i & 1)) && (i > 5)) ans[++tp] = (int) (1LL * g * C % M * C % M);
      f0 = f1,f1 = g;
  }
  sort(ans + 1,ans + tp + 1);
  for (int i = 1;i <= tp;i ++) if ((ans[i] != ans[i - 1]) || (i == 1)) cnt ++;   
  printf("%d\n",cnt % M);
}