【斐波拉契+数论+同余】【ZOJ3707】Calculate Prime S

题目大意：

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\n",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\n",temp/X);

    }

    return 0;

}

巴特西

【斐波拉契+数论+同余】【ZOJ3707】Calculate Prime S

最新文章

热门文章