快速幂

bangbang-ande

### 第六部分 快速幂

快速幂的基本问题如下：

问题描述：
已知三个数：a，b，p，求a^b％p的值
数据输入：10 9 3
数据输出：1
数据范围：1≤a,b,p≤10^9

快速幂算法是高精度中的异类，因为他不同于前四个程序的书写，
快速幂算法逻辑相同，就是数据大小会影响程序的不同。

上面的题目相信大家就看明白了，我们接下来需要开始想想-解这道题应该怎么解？

第一个思路就是简单的直接算：先按照乘方一遍一遍乘，接着再用除法的程序。
这个思路是可以写出来程序，但是有两个关键问题：一个是好不好写，很明显，写一个高精度乘法+高精度除法+主函数很有难度，相当于让你重新练一遍代码。还有一个更加关键的问题就是：这么写，当遇到大数的时候，那多乘几次就废了（复杂度大约为O(n^2)），很容易超时。

第二个思路可以简化难写的问题，乘一次，取余一次，这样子有效规避了乘法所带来的难题，复杂度有所改善（从O(n^2)变到了O(n)），稍微比较好，但是有些题用O(n)是过不去的，例如1000000000^1000000000。（在洛谷P1226中只有50-80分），而且还有，如果数据没有基本问题那么小，开到上千位的话，恐怕就得用回第一种方法了。

这两个比较简单的思路都很难过关，所以我们就得想想其他做法了：
我们用数学的思维可以来想：100^100=(100^2)^50
100和100^2都比较好算，所以我们可以这么做：
把一个数的n次方化作多个1次方或平方，然后再分别取模，那这样子就很容易过了

举个例子：
3^30
=(3^15)^2
=(3^14×3)^2
=((3^7)^2×3)^2
=((3^6×3)^2×3)^2
=((3^3)^2×)^2×3)^2
=((3^2×3)^2×3)^2×3)^2

所以——
一个数的n次方，就可以用逐步的递归拆成这个数的一次方或平方的多次乘积的结果。

那么这个拆分有一个很显而易见的规律：
如果这个数的指数是偶数，那么他拆分的结果就是这个数的（指数/2）次方的平方
如果这个数的指数是奇数，那么拆分的结果就变成了这个数的（指数/2）次方的平方在乘以这个数

所以大家理解了吗？
代码运用了递归的方法写，大家可以参考一下

特别注意：所有的代码在附件中

因为过于难写的原因，这里就不写高精度式的了，其实简单来说，高精度式的就是在此基础上增添高精度乘法与高精度除法罢了，大家可以尝试一下。


推荐练习题：洛谷P1226，P1045

zhangjinxuan

主要是运用了如下性质：

b 为偶数：
a^b = (a^2)^(b/2)。

b 为奇数
a^b = (a^2)^(b/2-1) * a。

知道了这两个，应该就特别好写了

sfqxx

zhangjinxuan 发表于 2023-7-12 20:51
主要是运用了如下性质：

b 为偶数：

收藏

额外减小

python好啊，自带ksm

pow(a,b,p)

这个效率很高，一般都能过。可惜西西弗不认python(悲)