快速幂/快速幂取模/矩阵求解快速幂

因为做了一个Fibonacci的题需要用矩阵+快速幂求解所以引发了下面一系列问题！！！

快速幂：

            快速幂时间复杂度为 O(log2N)， 与朴素的O(N)相比效率有了极大的提高。

            例如：

 代码：

  

   

    

     

    
    

     

      #include <stdio.h>
     
    
   

    

     

    
    

     

      int power(int n, int k)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int ans = 1;
     
    
   

    

     

    
    

     
	while( k )
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		if(k&1)
     
    
   

    

     

    
    

     

      			ans *= n ;
     
    
   

    

     

    
    

     

      		k= k/2;
     
    
   

    

     

    
    

     

      		n *= n;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	return ans ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main ( ) 
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int n, k;
     
    
   

    

     

    
    

     
	while(scanf("%d %d",&n, &k)!=EOF)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
 printf("%d\n",power(n,k));
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 
     
    
  
 

快速幂取模：

       快速幂取模还不算太懂，只知道需要对每一个值取模，公式 a*b%c=((a%c)*b)%c 。

代码：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 long long a,b,c,d;
     
    
   

    

     

    
    

     
 int T;
     
    
   

    

     

    
    

     
 scanf("%d",&T);
     
    
   

    

     

    
    

     
 while(T--)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%lld%lld%lld",&a,&b,&c);
     
    
   

    

     

    
    

     
 long long  ans=1;
     
    
   

    

     

    
    

     
 while( b )
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if( b%2 )
     
    
   

    

     

    
    

     

       ans = ( ans * a ) % c;
     
    
   

    

     

    
    

     

       b/=2;
     
    
   

    

     

    
    

     

       a = ( a * a ) % c;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 printf("%lld\n",ans);
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

矩阵+快速幂 求解Fibonacci数列：

           矩阵：矩阵可以看成一个n×m的数表，用二维数组表示
           矩阵乘法：定义矩阵A,B。A和B可以乘法操作当且仅当A的大小是a×b，B的大小是b×c，设矩阵C=AB，则C的大小是a×c，

        且有：

            最普通的矩阵乘法是直接三个for循环直接计算而已，所以复杂度是O（n3）.

            
  运用矩阵乘法快速幂，可以快速计算出矩阵B^(n-1),这样实现将时间复杂度降低到O(log n).

代码（nyoj 698题 A Coin Problem 别人优代码 ）：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      #include<string>
     
    
   

    

     

    
    

     

      #include<cstring>
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     

      const int Max = 10000;
     
    
   

    

     

    
    

     

      struct M
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
   long long p[2][2];
     
    
   

    

     

    
    

     

      };
     
    
   

    

     

    
    

     

      M mult(M a,M b)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int i,j,k;
     
    
   

    

     

    
    

     

       M c;
     
    
   

    

     

    
    

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

    

     

    
    

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

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       c.p[i][j]=0;
     
    
   

    

     

    
    

     
 for(k=0;k<2;k++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       c.p[i][j]=(c.p[i][j]+a.p[i][k]*b.p[k][j]%Max)%Max;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return c;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      M pow(M a,long long k)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

       M b={1,0,0,1};
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 while(k)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(k&1)
     
    
   

    

     

    
    

     

       b=mult(b,a);
     
    
   

    

     

    
    

     

       a=mult(a,a);
     
    
   

    

     

    
    

     

       k>>=1;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return b;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int t;
     
    
   

    

     

    
    

     
 long long n;
     
    
   

    

     

    
    

     
 scanf("%d",&t);
     
    
   

    

     

    
    

     
 while(t--)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 scanf("%lld",&n);
     
    
   

    

     

    
    

     

       M a={1,1,1,0};
     
    
   

    

     

    
    

     

       M c;
     
    
   

    

     

    
    

     

       c=pow(a,n-1);
     
    
   

    

     

    
    

     
 printf("%lld\n",(c.p[0][0]*2+c.p[0][1]*1)%Max);
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

还不明白请点击~>
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/9335585