hdu4549_M斐波那契数列解题报告

Solution：

1.快速幂：数/矩阵

2.以证明1000000007是素数。

费马小定理：

若p是素数，gcd(a,p)=1,则a^(p-1)1(mod p)。

若a^b mod p 中b很大，则可以简化为a^b mod p=a^[b mod (p-1)] mod p

证明如下：

b=t*(p-1)+r，其中r为b除以(p-1)的余数，即为b mod (p-1)。

a^b=(a^(p-1))^t * a^r 1^t * a^r a^r (mod p)

费马小定理的推广：如果p为质数，x^p-x（x是任意正整数）必能被p整除

注意是对b，对结果分别是取模(p-1)，取模p；不要同时取模p或同时取模(p-1)！

 #include <stdio.h>

 #include <stdlib.h>

 #define yu_ 1000000006

 #define yu 1000000007

 int main()

 {

     //f[n]=a^x(n-1)*b^x(n)

     //a^f(n-1) = a^(f(n-1)%1000000006) (mod 1000000007)

     //1000000007 is a prime

     long n,nn,w,i,c[];

     __int64 x[],y[],u[],v[],p,q,s,t,pp,qq,ss,tt,a,b,result;

     x[]=;

     y[]=;

     u[]=;

     v[]=;

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

     {

         x[i]=(x[i-]*x[i-]+y[i-]*u[i-])%yu_;

         y[i]=(y[i-]*(x[i-]+v[i-]))%yu_;

         u[i]=(u[i-]*(x[i-]+v[i-]))%yu_;

         v[i]=(y[i-]*u[i-]+v[i-]*v[i-])%yu_;

     }

     while (scanf("%ld%ld%ld",&c[],&c[],&n)!=EOF)

     {

         if (n==)

         {

             printf("%ld\n",c[]);

             continue;

         }

         else if (n==)

         {

             printf("%ld\n",c[]);

             continue;

         }

         result=;

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

         {

             p=;

             q=;

             s=;

             t=;

             //a:n-2 b:n-1

             nn=n+i-;

             w=;

             while (nn)

             {

                 if ((nn & )==)

                 {

                     pp=p;

                     qq=q;

                     ss=s;

                     tt=t;

                     p=(pp*x[w]+qq*u[w])%yu_;

                     q=(pp*y[w]+qq*v[w])%yu_;

                     s=(ss*x[w]+tt*u[w])%yu_;

                     t=(ss*y[w]+tt*v[w])%yu_;

                 }

                 w++;

                 nn>>=;

             }

             //f(n)/f(n+1)

             p=(p+q)%yu_;

             a=;

             b=c[i];

             while (p)

             {

                 if ((p & )==)

                     a=(a*b)%yu;

                 p>>=;

                 b=(b*b)%yu;

             }

             result=(result*a)%yu;

         }

         printf("%I64d\n",result);

     }

     return ;

 }

巴特西

hdu4549_M斐波那契数列解题报告

最新文章

热门文章

巴特西

hdu4549_M斐波那契数列 解题报告

最新文章

热门文章

hdu4549_M斐波那契数列解题报告