题目大意：
S[n] 表示 集合{1,2,3,4,5.......n} 不存在连续元素的子集个数
Prime S 表示S[n]与之前的所有S[i]互质;
问 找到大于第K个PrimeS 能整除X 的第一个S[n]
并且 输出(S[n]/X)%M
1.斐波拉契阶段
很容易写出S[n]的各个值发现是斐波拉契数列
2 3 5 8 13 21 34
2.斐波拉契性质
gcd(fib(n),fib(m))=fib(gcd(n,m)) （从1开始计算的即 1 1 2 3 5 8序列）
所以只有当 gcd(n,m)=1或2时 fib[n]与fib[m]互质
S[n]=fib[n+2]
所以若S[n] 要是一个 PrimeS
则n+2必须是一个质数或者4 ，自己画画就知道为什么4是特殊的了
所以构造一个特殊的素数表
P[i] 3 4 5 7 11 13...................
所以第K个PrimeS 就是fib[P[k]]
3.如何寻找整除X的数
从 fib[P[k]开始一个一个找 使得fib[P[k]]%X==0 的数即可
记录ansi=i；
4.同余公式的引用
(a/b)%c=（a%（b*c））/b
根据ansi 计算即可
代码如下：
/*
TLE 1次
没注意1000000个质数 maxn 至少要1600W
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#define oo 0x13131313
#define LL long long
using namespace std;
const int maxn=16000001;
int K,X,M;
int p[2000001],tot=0;
bool yn[maxn];
struct node{
LL mat[3][3];
};
node matmult(node a,node b,int mod)
{
node c;
memset(c.mat,0,sizeof(c.mat));
for(int i=1;i<=2;i++)
for(int j=1;j<=2;j++)
for(int k=1;k<=2;k++)
c.mat[i][j]=(c.mat[i][j]+a.mat[i][k]*b.mat[k][j])%mod;
return c;
}
node quickmatpow(node a,int n,int mod)
{
node c;
memset(c.mat,0,sizeof(c.mat));
c.mat[1][1]=1;c.mat[1][2]=0;c.mat[2][1]=0;c.mat[2][2]=1;
while(n!=0)
{
if(n&1==1) c=matmult(c,a,mod);
a=matmult(a,a,mod);
n=n>>1;
}
return c;
}
void get_prime()
{
for(int i=2;i<maxn;i++)
{
if(yn[i]==false)
{
p[++tot]=i;
for(int j=i;j<maxn;j=j+i)
yn[j]=true;
}
}
// printf("%d
",tot);
p[1]=3;
p[2]=4;
}
void init()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
}
int main()
{
// init();
get_prime();
int T;
cin>>T;
while(T--)
{
int ansi;
int temp;
node a,c;
memset(a.mat,0,sizeof(a.mat));
memset(c.mat,0,sizeof(c.mat));
a.mat[1][1]=1,a.mat[1][2]=1,a.mat[2][1]=1,a.mat[2][2]=0;
scanf("%d%d%d",&K,&X,&M);
for(int i=p[K];;i++)
{
c=quickmatpow(a,i-2,X);
temp=((c.mat[1][1]+c.mat[1][2]))%X;
if(temp==0)
{
ansi=i;
break;
}
}
c=quickmatpow(a,ansi-2,M*X);
temp=((c.mat[1][1]+c.mat[1][2]))%(M*X);
printf("%d
",temp/X);
}
return 0;
}