【详解】快速幂&龟速乘&快速乘
如果不会。。。。那我们现在开始讲吧（要不然为什么叫详解2333 ）
如果已经知道，就跳到下面去看吧~
1. 快速幂
1.0 快速幂的诞生——最初的思路
我们通常需要求解形如 ab mod c 的式子，当b比较小的时候，我们通常可以想到用循环乘来解决这个问题，就像这样：
long long a,a1,b,c;
cin>>a>>b>>c;
a1=a;
for(int i=1;i<=b;i++)
a*=a1,a%=c;
cout<<a;
- 1
- 2
- 3
- 4
- 5
- 6
显然这个的时间复杂度是O（b）的，在平时基本够用了。
不过在某些大型的数据结构题里面（比如无良的线段树 ），这样的计算随处可见，假设那个b大一点，比如1e7,1e8之类的，然后再重复上几百几千次……
比如这个例子：
23333 123456787654321 19260817
你可以试着拿刚才那个循环跑一下（微笑）
如果你把数据中的b换成123454321，也就只需要跑2.8s而已（微笑x2）
所以，正是为了解决这样的问题，快速幂出现了。
1.1 快速幂的根据——二进制
没错，快速幂和我们的老朋友二进制又扯上关系了。
其主要原因是因为二进制一个很重要的性质，就是当十进制转化为二进制，会出现很有趣的地方。
我们来看这两个例子：
11= 8+2+1 =23+21+20
34= 32+2 =25+21
如你所见，它们可以拆成很多个2n的和。这是废话
我们再来看这两个例子:
311=38 ×××× 132
有没有嗅到一丝危险的气息 发现什么有趣的东西?
1.2 快速幂的实现——位运算
如果你已经理解到它与二进制的关系，那么接下来的代码就很容易懂了：
//计算 (x^y)%mod
long long quick_pow(long long x,long long y,long long mod)
{
long long sum=1;
while(y!=0){
if(y&1==1)sum=sum*x%mod;
x=x*x%mod;
y=y>>1;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
（其实从我个人角度来说，一般在初学某个知识点时看到模板里面有位运算会感到头疼。不过，跟二进制相关的一些东西需要例外，因为这样反倒会更加容易理解）
代码看不懂？没关系，我们举个例子就好了，就用上面的311来说：
- 开始前：x=3 y=(1011)2=11;
- 第一轮：11&1=1,sum=3, x=9, y=(1011>>1)2=(101)2=5;
- 第二轮：5&1=1，sum=27, x=81,y=(101>>1)2=(10)2=2;
- 第三轮：2&1=0，sum=27,x=6561,y=(10>>1)2=(1)2=1;
- 第四轮：1&1=1,sum=177147,x=65612,y=(1>>1)2=(0)2=0;
- 循环结束，退出，得到sum=311=177147.
看到了吗？原本循环11次的算法被优化成了循环五次，而且由于与二进制相关联，指数b每一次减少一半，也就是说这个算法的时间复杂度是 O（logN）！log级别的算法代表什么，我不说大家也清楚~
所以，刚才的那个例子你可以拿来试试，博主不懂怎么测程序运行时间，只会加文件输入输出。 在本机上跑只花了0.57s，比起刚才的时间明显是大大优化了。
1.3快速幂总结——二进制大法好
二进制，在我们学习的道路上一直起着很大的用处，无论是加快运行的速度的位运算，或是快速处理前缀和的树状数组，还是今天提到的快速幂，都灵活运用了二进制的特性，从而大大优化了我们处理某些问题时浪费的时间和空间。
没错，快速幂的核心思想就是通过二进制的特有属性，先把次数转化为二进制，然后把那些为1的位（有贡献的）存下来，把为0的位（无贡献的）丢弃。我们之所以要进行这样的循环，就是为了依次处理出那些为1的位，然后累乘到答案里面。
实际上，快速幂的应用范围不止求ab mod c这一种，矩阵快速幂就是它的一个变式，有兴趣的同学可以去了解一下，在处理很多数学问题时非常有用。
（而且似乎也是考点之一？？）
那么，了解了快速幂的这些思想，我们就要开始挑刺思考它被hack的可能性了。
2.龟速乘
2.0 龟速乘的诞生——快速幂的BUG
假设给你一个ab mod c的式子，现在的你已经可以说：我能够在log b的时间里算出来！
了吗？（和善的眼神x2）
你确定吗？（和善的眼神x3）
来来来，算一算这个，看看你的快速幂还活着不：
19260817 2333333 1234567654321
（我会说我只是把数字换了下顺序吗）
很好，现在我们找到了快速幂的一个大问题：当模数>1e9的时候，光是在相乘的时候就已经爆long long了。（当然你可以用__int128，不过NOIP似乎不允许 ）
那怎么办？我们不能用快速幂了吗？
事实上想用还是可以的，不过看看标题，你就知道为了适应新的数据范围，我们需要付出什么代价了……
2.1 龟速乘的根据&实现——慢工出细活
比起计算机自带的乘法，龟速乘的的运行速度还要慢上一些。
但是，它可以有效地保证你的long long不会boom的一声炸掉，然后送给你一个神奇的数字。
代码奉上：
long long quick_mul(long long x,long long y,long long mod)
{
long long ans=0;
while(y!=0){
if(y&1==1)ans+=x,ans%=mod;
x=x+x,x%=mod;
y>>=1;
}
return ans;
}
long long quick_pow(long long x,long long y,long long mod)
{
long long sum=1;
while(y!=0){
if(y&1==1)sum=quick_mul(sum,x,mod),sum%=mod;
x=quick_mul(x,x,mod),x%=mod;
y=y>>1;
}
return sum;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
相信你一眼就能看出来，这两个东西长的不是一般的像。
如果再仔细观察一下就会发现，快速幂里的x是指数级增长，而龟速乘变成了翻倍，仅此而已。
2.2 龟速乘总结——快速幂的补充
实际上，龟速乘的确慢，甚至比直接用开始提到的循环乘法还要慢（因为龟速乘相当于一个自行取模的乘号），然而慢工出细活，正是它的慢最终为我们解决了数据过大时产生的问题。
归根结底，龟速乘的出发点就是为了解决弥补快速幂的BUG，因而其思想与快速幂也十分接近。用一点点时间换来数据范围的扩大，想来是个不亏的交易。
当然，平时不担心爆long long的情况下，就没必要把龟速乘加上了~
讲了这么多，我们再看看最上面的标题，
貌似还有个压轴的东西没有讲……
3.快速乘
3.0快速乘的诞生—— 更精练，更简短
人们在研发出上面龟速乘以后，再也不用为了次方运算+取模的题型烦恼了……
然而，总是有人不满足：
就为了这种小问题，要我再多背那么长的模板？我才不干！
（以上纯属yy ）
真相到底是什么我们无从知晓，但我们清楚的是结果：
那就是复杂度为O（1）的，一行可以打完的，快速乘的诞生。
3.1快速乘的根据——long double和long long的转换
这一部分也是刚刚学到，所以我只能找网上的资料了：
这是2009国家集训队论文：
骆可强：《论程序底层优化的一些方法与技巧》 （%%%）
说白了，其实我们就是在原地爆炸的边缘疯狂试探，把本来存进long long会炸掉的值先进行计算，用long double暂时存下，然后再把差值——一个不会超过long long的数字塞回去，再特判一下精度问题，就大功告成了。
所以，在压行之后就变成了这样：
cin>>a>>b>>mod;
cout<<((a*b-(long long)((long double)a*b/mod)*mod+mod)%mod);
- 1
- 2
简洁明了，速度O（1），不过数值过大时容易造成误差，毕竟long double转换时会有精度上的误差，所以在真正要用的时候，还是建议大家使用龟速乘吧
(不过听说机房大佬dzyo用过几次都没什么事，emmm……)
至此，三种与幂运算相关的算法就全部讲完啦~
（P.S：博主第一篇讲解贴，若有不足敬请指出！顺便谢谢各位观看！）
</div>
<link href="https://csdnimg.cn/release/phoenix/mdeditor/markdown_views-7b4cdcb592.css" rel="stylesheet">
</div>
</article>
京公网安备 11010502036488号