zoj3707(Calculate Prime S)解题报告

1.计算(a/b)%c，其中b能整除a

设a=b*r=(bc)*s+b*t

则(b*t)为a除以bc的余数

r=c*s+t

而

(a/b)%c=r%c=t

(a%bc)/b=(b*t)/b=t

所以对于b与c互素和不互素都有(a/b)%c=(a%bc)/b成立。

当bc不大时，先取模bc，再除b

如果b与c互素，则(a/b)%c=a*b^(phi(c)-1)%c

待证

2.与集合子集

斐波那契数列的第n+2项同时也代表了集合{1,2,...,n}中所有不包含相邻正整数的子集个数。

证明：归纳法证明——

n=1时，相应子集个数为2，为f(3)；

n=2时，相应子集个数为3，为f(4);

n>=3时，若集合{1,2,...,n-2}的相应子集为f(n)，集合{1,2,...,n-1}的相应子集为f(n-1)

则对于集合{1,2,...,n}：

包含n的子集(即不包含n-1，在最大项可以为n-2的子集基础上加上数字n)个数为f(n)

不包含n的子集个数为f(n+1)(最大项可以为n-1的子集)

所以集合{1,2,...,n}的相应子集为f(n)+f(n+1)=f(n+2)

所以得证

3.gcd(fib(n),fib(m))=fib(gcd(n,m))

证明：http://www.cnblogs.com/cmyg/p/6618893.html

当一个数n与其它数m的最大公约数为为1或2时，则fib(n)和fib(m)的最大公约数为fib(1)或fib(2)，为1。

 #include <stdio.h>

 #include <stdlib.h>

 #include <stdbool.h>

 #include <malloc.h>

 #include <memory.h>

 #define ansnum 20000000

 #define anszhi 2000000

 struct node

 {

     long long mat[][];

 };

 long *zhi;

 bool *vis;

 long yu;

 void Prime()

 {

     long i,j,ans=;

     memset(vis,true,sizeof(bool)*ansnum);

     for (i=;i<ansnum;i++)

     {

         if (vis[i])

         {

             ans++;

             zhi[ans]=i;

         }

         for (j=;j<=ans;j++)

         {

             if (i*zhi[j]>=ansnum)

                 break;

             vis[i*zhi[j]]=false;

             if (i%zhi[j]==)

                 break;

         }

     }

     zhi[]=;

     zhi[]=;

 }

 struct node count_mat(struct node a,struct node b)

 {

     long i,j;

     struct node c;

     for (i=;i<;i++)

         for (j=;j<;j++)

             c.mat[i][j]=(a.mat[i][]*b.mat[][j]

                 +a.mat[i][]*b.mat[][j])%yu;

     return c;

 }

 long fib(long t)

 {

     struct node m,r;

     m.mat[][]=;

     m.mat[][]=;

     m.mat[][]=;

     m.mat[][]=;

     r.mat[][]=;

     r.mat[][]=;

     r.mat[][]=;

     r.mat[][]=;

     t--;

     while (t)

     {

         if ((t & )==)

             r=count_mat(r,m);

         t>>=;

         m=count_mat(m,m);

     }

     return (r.mat[][]+r.mat[][])%yu;

 }

 int main()

 {

     vis=(bool *) malloc (sizeof(bool)*ansnum);

     zhi=(long *) malloc (sizeof(long)*anszhi);

     long n,k,x,m,i,j;

     Prime();

     scanf("%ld",&n);

     for (i=;i<=n;i++)

     {

         scanf("%ld%ld%ld",&k,&x,&m);

         yu=x;

         for (j=zhi[k];;j++)

             if (fib(j)==)

                 break;

         yu=x*m;

         printf("%ld\n",fib(j)/x);

     }

     return ;

 }

 /*

 5

 5 13 10

 1 11 3

 5 2 5

 5 5 6

 1000000 100 1000000

 */

巴特西

zoj3707(Calculate Prime S)解题报告

最新文章

热门文章