我们前面一篇文章学习了快速幂。它可以解决两类问题：

• a^b，

• (a^b)%c

对于第一类，我们可以使用递归法或者迭代法可以求出，为了计算的快，我们可以引入位运算操作，但是目前来看，无论怎么优化都不能超过long long。

对于第二类，是快速幂的优点所在，通过 （a*b）%m=(a%m *　ｂ％ｍ)　％ｍ公式，我们可以将结果运算范围大大减小，使运算结果保持在m范围以内。

但是，快速幂并不是万能的，比如下面这个例子求（ａ＾ｂ）％ｍ。

19260817 2333333 1234567654321

也就是（19260817^233333）%1234567654321。那么很明显，快速幂也会爆掉。因为取模的数> 1e9后，两个数相乘就会爆 long long了（高精度除外）。

那么这样的题目应该怎么处理，这就是我们今天的主角：龟速乘。

一、龟速乘

简单来说，当形如 （a*b）%c这种表达式进行求解计算时，如果a,b的值都>=1e9，特别当c的值也>=1e9时，long long 会爆掉，此时采用龟速乘的方式来进行计算。

顾名思义，龟速乘是比较慢的，主打的就是 慢工出细活

代码模板如下：

long long slowmul(long long x,long long y,long long mod) {  	long long ans=0;  	while(y) {  		if(y&1==1){  		 ans+=x;  		 ans%=mod;  		}  		x=x+x;  		x%=mod;  		y>>=1;  	}  	return ans;  }

二、龟速乘原理

要知道龟速乘的原理，首先要回到小学阶段一开始讲乘法原理的时候：乘法的本质就是加法

比如下面这个例子：

我们计算3*5。

3*5 = 3*(4+1)   //这个地方为什么是4+1，而不是2+3？      = 3*4 + 3*1    //看到这里，有没有什么想法  //如果没有，我们借助一个图来清楚描述一下刚才的过程  7*13=3*(8+4+1)

上面的这个过程，1 1 0 1 对应 8 4 2 1。非常巧合的一件事，8 4 2 1 就是2^3、2^2、2^1、2^0。很显然，我们回到了二进制，而龟速乘就是利用了这个原理来进行操作的。

在上面的过程中，8 4 2 1是二进制中基，从左往右是除2，从右往左是乘2，对应的二进制操作中右移和左移。

那么我们再来详细看看代码是怎么处理的。

我们用这种方法求7*13：

int slowMult(int a,int b){ //a为基底，b为乘数，即a*b  	int ans=0; //ans即最终结果  	while(b) {  		if(b&1)   			ans+=a; // 判断二进值是否为1  		a+=a; //基底乘2  		b>>=1;//位运算  	}  	return ans;  }

注意，此方法区别于我们前面讲的迭代法求快速幂。

//迭代法求快速幂，求a^b  #include<bits/stdc++.h>  using namespace std;  long long pow_d(long  a,long  b){      long ans=1;      while(b>0){          if(b&1){//如果b的二进制末尾为1 ，就相当于被选中了。          //就如2^13 ==> 2^(13==>1101)==> 2^(1101) ==> 3 2 0 号为 1 那么被选中 ==> 2^13 = 2^8 *  2^4 * 2^1              ans=ans*a;//令ans累积上a           }          a=a*a;//令a平方           b>>=1;//将b的二进制右移一位即       }      return ans;  }  int main(){      long long  a,b;      cin>>a>>b;       long long  result=pow_d(a,b);      cout<<result<<endl;

区别：快速幂里的x是指数级增长，而龟速乘变成了翻倍。

我们再回来看(a*b)%c

long long slowmul(long long x,long long y,long long mod) {  	long long ans=0;  	while(y) {  		if(y&1==1){  		 ans+=x;  		 ans%=mod;  		}  		x=x+x;  		x%=mod;  		y>>=1;  	}  	return ans;  }

(adsbygoogle = window.adsbygoogle || []).push({});