题意：定义了S[n]为{1,2,...,n}的非连续数字的子集的个数，然后对于每个S[n]，如果对于每个1<=i<n，gcd(S[i],S[n])=1，则称S[n]是素的S。对于第k个素的S，找到一个最小的S[n]，使得S[n]是x的倍数，并且S[n]>=第k个素的S。然后输出(S[n]/x)%m。
首先证明几个结论。
I. gcd(ab,c)=gcd(a,c) 当gcd(b,c)=1时。
证明：gcd(ab,c)=gcd(a,c)*gcd(b,c)=gcd(a,c)
II. gcd(a,b)=gcd(b, a%b)。
证明：假设a>=b，则a=nb+m。假设g|a，g|b，所以g|(nb+m)，所以g|m。因为a%b=(nb+m)%b=m，所以得证。
III. gcd(fib(i),fib(i+1))=1。
证明：因为fib(i+1)=fib(i)+fib(i-1)，
所以gcd(fib(i),fib(i+1))=gcd(fib(i),fib(i)+fib(i-1))=gcd(fib(i),(fib(i)+fib(i-1))%fib(i))=gcd(fib(i),gcd(fib-1))，
可以把euclid的过程给展开，得到：
fib(i+1)=1*fib(i)+fib(i-1)
fib(i)=1*fib(i-1)+fib(i-2)
fib(i-1)=1*fib(i-2)+fib(i-3)
......
fib(4)=1*fib(3)+fib(2)
fib(3)=2*fib(2)+0
最后一行写出来就是：
2 = 2*1+0
所以gcd(fib(i),fib(i+1))=fib(2)=1;
英文原文证明以及反证法参考：
Consecutive Fibonacci Numbers Relatively Prime
http://mathforum.org/library/drmath/view/52716.html
IV. fib(u+v)=fib(u)fib(v-1)+fib(u+1)fib(v).
证明：利用反证法。
当u=1时：fib(1+v)=fib(1)fib(v-1)+fib(2)fib(v)=fib(v-1)+fib(v) 成立。
假设u=n时成立：fib(n+v)=fib(n)fib(v-1)+fib(n+1)fib(v) 成立。
u=n+1时：
fib(n+1+v)=fib(n+v)+fib(n+v-1)=fib(n)fib(v-1)+fib(n+1)fib(v) + fib(n-1)fib(v-1)+fib(n)fib(v)
=fib(v-1)(fib(n)+fib(n-1)) + fib(v)(fib(n-1)+fib(n)) = fib(n+1)fib(v-1)+fib(n+2)fib(v) = fib(n+1+v)
所以，由数学归纳法可以得证。
英文原文证明以及Binet Formula证明参考：
http://mathforum.org/library/drmath/view/51624.html
V. fibonacci-gcd proof: gcd(fib(n),fib(m))=fib(gcd(n,m)).
证明：假设n<=m，则: gcd(fib(n),fib(m))=gcd(fib(n),fib(n+k))，由证明IV，可得：
gcd(fib(n),fib(n+k))=gcd(fib(n),fib(n)fib(k-1)+fib(n+1)fib(k))
=gcd(fib(n),(fib(n)fib(k-1)+fib(n+1)fib(k))%fbi(b))
=gcd(fib(n),fib(n+1)fib(k))，由证明III，gcd(fib(b),fib(n+1))=1，所以由证明I可得：
gcd(fib(n),fib(n+1)fib(k))=gcd(fib(n),fib(k))，所以可得：
gcd(fib(n),fib(m))=gcd(fib(n),fib(m%n))。由展开euclid算法可知，算法在gcd(fib(g),fib(0))时停止，而g=gcd(m,n)。
所以由euclid算法的定义可得gcd(fib(g),fib(0))=fib(g)。
所以得证gcd(fib(n),fib(m))=fib(gcd(n,m))
英文原文证明参考：
http://mathforum.org/library/drmath/view/61690.htmlVI. (a/b)%c=(a%bc)/b 当 b|a。
证明：因为b|a，所以a=kb。
左边=(a/b)%c=(kb/b)%c=k%c。
右边=(kb%bc)/b=((k%c)b)/b=k%c。
所以得证。
VII. fibonacci的一个结论：
矩阵快速幂即可。
VIII. 又一个结论，因为x很小（x<=100），所以能在题目给定的时间内枚举到所需的S[n]。
至此，此题需要的证明已齐，只需要素数筛法预处理出所有的位数，然后再暴力枚举即可。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define LL long long
using namespace std;
const int N = 15486042;
int MOD;
int prime[1001000], top;
bool isnot[20010000];
int ncase;
int k, x, m;
LL now, next;
struct Matrix
{
LL ma[2][2];
Matrix()
{
ma[0][0]=ma[1][1]=1;
ma[0][1]=ma[1][0]=0;
}
void init()
{
ma[0][0]=ma[1][0]=ma[0][1]=1;
ma[1][1]=0;
}
Matrix
operator * (
const Matrix &a)
const {
Matrix res;
for (
int i = 0 ; i < 2 ; i++ )
for (
int j = 0 ; j < 2 ; j++ )
{
res.ma[i][j]=0;
for (
int k = 0 ; k < 2 ; k++ )
res.ma[i][j]=(res.ma[i][j]+ma[i][k]*a.ma[k][j])%MOD;
res.ma[i][j]%=MOD;
}
return res;
}
};
void init_prime()
{
memset(isnot,0,
sizeof(isnot));
top = 1;
for (
int i = 2 ; i < N ; i++ )
if (!isnot[i])
{
prime[top++]=i;
if (i<10000)
for (
int j = i+i ; j < N ; j+=i )
isnot[j]=1;
}
prime[1]=3;prime[2]=4;
}
void init(
int k)
{
Matrix res, a;
a.init();
while (k)
{
if (k&1)
res = res*a;
a=a*a;
k>>=1;
}
next = (res.ma[0][0]+res.ma[1][0])%MOD;
now = (res.ma[0][1]+res.ma[1][1])%MOD;
}
int main()
{
init_prime();
scanf("%d", &ncase);
while (ncase--)
{
scanf("%d%d%d", &k, &x, &m);
MOD = x*m;
init(prime[k]);
while (now%x)
{
swap(now,next);
next = (now+next)%MOD;
}
printf("%lld\n", now/x);
}
return 0;
}