这道题目真的很难啊，不是那么好做的，现场比赛若是遇到这个 真心很难去花时间研究，我做了好久 WA了 10多把终于过了
总是做算法，不如来个陶冶情操的文章一篇： http://www.sanwen.net/subject/3628849/
有一个集合{1,2,3,,,n}, Sn表示 他的特殊子集数（子集中元素不允许出现连续的现象），比如 {1,2}这个就是非法的，Sn与前面所有的Si都互素的sn叫做 PRIME S，
求不小于第K个PRIME S的 能被X整除的数 对M取模的结果
我的想法没那么高深，一开始就按照题目要求，列举找出SN的值，后来多写几个 发现了 是 fibonacci数列，题目中把 Sn与前面所有的Si都互素的sn叫做 PRIME S，再在 fibonacci数列里找找，发现 其实如果 F[n]是素数的话 那么 就满足题目要求，那么其实F[n] 是PRIME S 当F[n] 为素数，所以 题目的大体方向救出来了，就是 fibonacci数列构造出来，但是K的最大值有10^6所以 不可能递推出来，可以用矩阵构造
构造矩阵 A[2][2] ={1,1,1,0}，这个在学矩阵快速幂的时候遇到过，用上了
对于输出还有一个特殊的地方 那就是 如果 X/Y%MOD,如果Y能够整除X，这个式子可以转化为 (X%(MOD*Y))/Y,证明
如果b与c互素，则(a/b)%c=a*b^(phi(c)-1)%c
如果b与c不互素，则(a/b)%c=(a%bc)/b
这只是我的一些过程 还有大牛的分析，可能更好：来自http://www.cnblogs.com/xinyuyuanm/archive/2013/05/29/3106627.html
fibonacci数列的性子：
1.gcd(fib(n),fib(m))=fib(gcd(n,m))
证明：可以通过反证法先证fibonacci数列的恣意相邻两项一定互素，然后可证n>m时gcd(fib(n),fib(m))=gcd(fib(n-m),fib(m))，递归可
求gcd(fib(n),fib(m))=gcd(fib(k),fib(l))，最后k=l，不然继承递归。K是通过展转相减法求出，易证k=gcd(n,m)，所以gcd(fib(n),fib(m))
=fib(gcd(n,m))。
2.如果fib(k)能被x整除，则fib(k*i)都可以被x整除。
3.f(0)+f(1)+f(2)+…+f(n)=f(n+2)-1
4.f(1)+f(3)+f(5)+…+f(2n-1)=f(2n)
5.f(2)+f(4)+f(6)+…+f(2n) =f(2n+1)-1
6.[f(0)]^2+[f(1)]^2+…+[f(n)]^2=f(n)·f(n+1)
7.f(0)-f(1)+f(2)-…+(-1)^n·f(n)=(-1)^n·[f(n+1)-f(n)]+1
8.f(m+n)=f(m-1)·f(n-1)+f(m)·f(n)
9.[f(n)]^2=(-1)^(n-1)+f(n-1)·f(n+1)
10.f(2n-1)=[f(n)]^2-[f(n-2)]^2
11.3f(n)=f(n+2)+f(n-2)
12.f(2n-2m-2)[f(2n)+f(2n+2)]=f(2m+2)+f(4n-2m) [ n〉m≥-1,且n≥1]
还有一个结论：
盘算(a/b)%c 其中b能整除a
如果b与c互素，则(a/b)%c=a*b^(phi(c)-1)%c
如果b与c不互素，则(a/b)%c=(a%bc)/b
对于b与c互素和不互素都有(a/b)%c=(a%bc)/b成立
#include<iostream>
#include<cstdio>
#include<list>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#include<cmath>
#include<memory.h>
#include<set>
#define ll long long
#define eps 1e-8
#define inf 0xfffffff
//const ll INF = 1ll<<61;
using namespace std;
//vector<pair<int,int> > G;
//typedef pair<int,int > P;
//vector<pair<int,int> > ::iterator iter;
//
//map<ll,int >mp;
//map<ll,int >::iterator p;
const ll N = 20000000;
bool isprime[N];
ll prime[N];
void init()//依据题目数据范围处理一定范围内的素数
{
ll k = 1;
memset(isprime,false,sizeof(isprime));
for(ll i=2;i<N;i++) {
if(!isprime[i]) {
prime[k++] = i;
for(ll j=i*2;j<N;j+=i)
isprime[j]=true;
}
}
prime[0] = 2;
prime[1] = 3;
prime[2] = 1000;
prime[3] = 5;
}
typedef struct {
ll m[2][2];
}Matrix;
Matrix per,tmp;
void clear() {
for(int i=0;i<2;i++)
for(int j=0;j<2;j++) {
per.m[i][j] = (i == j);
if(i == j && i == 1)
tmp.m[i][j] = 0;
else
tmp.m[i][j] = 1;
}
}
Matrix multi(Matrix a,Matrix b,ll MOD) {
Matrix ans;
for(ll i=0;i<2;i++) {
for(ll j=0;j<2;j++) {
ans.m[i][j] = 0;
for(ll k=0;k<2;k++) {
ans.m[i][j] += a.m[i][k] * b.m[k][j];
ans.m[i][j] %= MOD;
}
ans.m[i][j] %= MOD;
}
}
return ans;
}
Matrix quick(ll k,ll MOD) {
Matrix ans = per;
Matrix p = tmp;
while(k) {
if(k&1) {
ans = multi(ans,p,MOD);
k--;
}
k >>= 1;
p = multi(p,p,MOD);
}
return ans;
}
int main() {
init();
ll k,X,MOD;;
int t;
scanf("%d",&t);
while(t--) {
clear();
Matrix ans;
scanf("%lld %lld %lld",&k,&X,&MOD);
ll i;
for(i = prime[k];i>=0;i++) {
ans = quick(i-1,X);
if(ans.m[0][0]%X == 0)break;
}
ans = quick(i-1,MOD * X);
ans.m[0][0] /= X;
printf("%lld\n",ans.m[0][0]);
}
return 0;
}
/*
100
1 3 10
2 3 103 3 10
101 117 100007 */
ZOJ3707 Calculate Prime S 数论好题目啊,布布扣,bubuko.com
ZOJ3707 Calculate Prime S 数论好题目啊
原文：http://blog.csdn.net/yitiaodacaidog/article/details/21743683