整数快速乘法/快速幂+矩阵快速幂+Strassen算法 一、整数运算：（快速乘法、快速幂） 二、矩阵运算：（快速幂）（Strassen算法有空再说）
快速幂算法可以说是ACM一类竞赛中必不可少，并且也是非常基础的一类算法，鉴于我一直学的比较零散，所以今天用这个帖子总结一下
快速乘法通常有两类应用：一、整数的运算，计算(a*b) mod c 二、矩阵快速乘法
先说明一下基本的数学常识：
(a*b) mod c == ( (a mod c) * (b mod c) ) mod c //这最后一个mod c 是为了保证结果不超过c
对于2进制，2n可用1后接n个0来表示、对于8进制，可用公式 i+3*j == n （其中 0<= i <=2 ），对于16进制，可用 i+4*j==n（0 <= i <=3）来推算，表达形式为2i 后接 j 个0。
接下来让我们尽可能简单的描述快速乘法的思想：
a*b
快速乘法的基本思想 ，是二进制和乘法分配律的结合，（不由得想起浮点数不满足结合律，严重吐槽！！！╮(╯-╰)╭），比如说，13 ==（1101）2 ，4*13等于4*（1101）2 ，用分配律展开得到4*13 == 4*（1000+100+1）2，我们不难观察出，快速幂可以通过判断当前的位（bit）是1还是0，推断出是否需要做求和操作，每次移动到下一位（bit）时，就对ans进行*2操作，等待是否求和。由于除以2和位移操作是等效的，因此这也可以看作是二分思想的应用，这种算法将b进行二分从而减少了不必要的运算，时间复杂度是log（n）。
a^b
快速幂其实可以看作是快速乘法的特例，在快速幂中，我们不再对ans进行*2操作，因为在a^b中b的意义已经从乘数变成了指数，但是我们可以仍然把b写成二进制，举例说明：此时，我们将4*13改为4^13，13=（1101）2 ，二进制13写开我们得到（1000+100+1），注意，这里的所有二进制是指数，指数的相加意味着底数相乘，因此有4^13 == 48 * 44 * 41。再注意到指数之间的2倍关系，我们就可以用很少的几个变量，完成这一算法。这样，我们就将原本用循环需要O(n)的算法，改进为O（logN）的算法。
按照惯例，给出尽可能简洁高效的代码实现 （以下所有int都可用long long 代替）
首先，给出快速乘法的实现：
1 //快速乘法 2 int qmul(int a,int b){// 根据数据范围可选择long long 3 int ans=0; 4 while(b){ 5 if( b&1)ans+=a;//按位与完成位数为1的判断 6 b>>=1;a<<=1;//位运算代替/2和*2 7 } 8 return ans; 9 }
如果涉及到快速乘法取模，则需要进行一些微小改动
改动所基于的数学原理，请参考红色字体标出的数学常识
1 //快速乘法取模 2 int qmul_mod(int a,int b,int mod){ 3 int ans=0; 4 while(b){ 5 if((b%=mod)&1)ans+=a%=mod;//这里需要b%=mod 以及a%=mod 6 b>>=1;a<<=1; 7 } 8 return ans%mod; //ans也需要对mod取模 9 }
接下来是快速幂的实现：
1 //快速幂 a^b 2 int qpow(int a,int b){ 3 if(a==0)return 0;//这是个坑，校赛被坑过，很多网上的实现都没写这一点 4 int ans=1; 5 while(b){ 6 if(b&1)ans*=a;//和快速乘法的区别 7 b>>=1;a*=a;//区别，同上 8 } 9 return ans; 10 }
以及含有取模的快速幂：
int qpow_mod(int a,int b,int mod){ if(a==0)return 0; int ans=1; while(b){ if(b&1)ans=(ans%mod)*(a%mod);//如果确定数据不会爆的话，可写成 ans*=a%=mod; b>>=1;a*=a%=mod;//等价于a=(a%mod)*(a%mod)，且将一个模运算通过赋值代替，提高了效率 } return ans%mod;//数据不会爆的话，这里的%运算会等价于第5中不断重复的 ans%mod }
如果我们对于性能还有更进一步的要求，那么也就是减少取模运算了，那么我们需要确定数据范围不会爆掉
在这样的前提下，我们可以只用原先1/4的取模运算量完成快速幂
int qpow_mod(int a,int b,int mod){ if(!a)return 0; int ans=1; while(b){ if(b&1)ans*=a%=mod;//这里的模运算只有一个 b>>=1;a*=a;//这里的模运算没有了 } return ans%mod; }
这些天找了好久，终于找到了纯粹的整数快速幂题目，按照惯例，给一波传送门：
poj1995：http://poj.org/problem?id=1995
这个题。。。没什么好说的，但是需要注意，用1/4模运算量的那种写法，数据会爆，所以必须写成完全取模的运算，这样程序会慢一点。。。呜呜呜，63ms水过，这是目前我做的最慢的了，如果大神知道如何在16ms及以下A掉它，欢迎联系我谢谢~o(*￣▽￣*)ブ
实现的代码如下：
1 #include<cstdio> 2 int z,a,b,m,h,sum; 3 int qpow_mod(int a,int b,int mod){ 4 if(!a)return 0; 5 int ans=1; 6 while(b){ 7 if(b&1)ans=ans%mod*(a%=mod); 8 b>>=1;a=a%mod*(a%mod); 9 } 10 return ans%mod; 11 } 12 int main(){ 13 scanf("%d",&z); 14 while(z--){ 15 scanf("%d%d",&m,&h);sum=0; 16 while(h--){ 17 scanf("%d%d",&a,&b); 18 sum+=qpow_mod(a,b,m); 19 sum%=m; 20 } 21 printf("%d ",sum); 22 } 23 }
先更新到这，有时间再更新矩阵的Strassen算法以及矩阵快速幂，，大家稍后见(●'◡'●)
2016-06-13 16:47:56
大家好，我又回来啦
二、矩阵运算：（快速幂）（Strassen算法有空再说）
矩阵的快速幂运算，其实思路和上面的整数快速幂是一样的，对指数进行二分，不过我们对于快速幂本身，可能既可以写成函数，也可以写成运算符重载，所以这里我写的是运算符的重载，毕竟重载练得少，得多练一练
首先我们可以定义一个矩阵数据结构，也可以直接用二维数组
1 #define N 100 2 struct matrix{ 3 int m[N][N]; 4 };
然后我们重载^运算符，完成矩阵m的b次幂的快速幂运算
这里为了我自己代码习惯，我重载了*和*=两种运算符，当然，在写的时候跪在了忘了写函数声明上，毕竟C++不是java，对于函数声明的顺序有依赖，so~大家记得写函数声明呦
代码如下
1 //矩阵的数据结构 2 struct matrix{ 3 int m[N][N]; 4 }; 5 matrix operator * (matrix ,matrix);//重载声明 6 matrix operator *= (matrix,matrix); 7 matrix operator ^ (matrix a,int b){ 8 matrix ans; 9 for(int i=0;i<N;i++) 10 for(int j=0;j<N;j++)ans.m[i][j]=(i==j);//初始化为单位矩阵 11 if(b&1)ans*=a; 12 b>>=1;a*=a; 13 return ans; 14 } 15 matrix operator * (const matrix a,const matrix b){//朴素矩阵乘法 16 matrix ans; 17 for(int i=0;i<N;i++) 18 for(int j=0;j<N;j++) 19 for(int k=0;k<N;k++) 20 ans.m[i][j]=a.m[i][k]+b.m[k][j]; 21 return ans; 22 } 23 matrix operator *= (matrix a,const matrix b){ 24 return a=b*b; 25 }
当然，有必要的时候，我会再更新一波Strassen算法，考虑到在很多情况下，Strassen算法反而会降低矩阵运算的速度，所以我们就先到这里~拜拜(●ˇ∀ˇ●)