快速幂取模算法

c/c++

浏览数:126

2019-6-8

快速幂的使用范围:指数型数据取模问题,int与longlong无法进行处理储存。此时须使用快速幂算法。
快速幂的思路:
引理: 积的取余等于取余的积的取余。 在这条引理上,对指数型数据进行拆分和合并,就是快速幂算法
快速幂具体分析: 1,对于base^index的数据,我们往往会因为base或index过大而无法处理。我们要想办法缩小base和index的规模,来逐个击破。 首先,我们先按照引理来进行代码实现

1 //base是底数,index是指数,mode是取模数,result是记录结果。
2 int result = 1;
3 base = base % mode;
4 for(int i = 1; i <= index; ++i)
5 {
6     result = result * a;
7 }
8 result = result % mode;

这是直接利用引理写出的代码,它的效果不是很理想,优化度也不高。我们是否可以继续拆分呢? 下面是我目前已知的最优的拆分合并方法。 2,我们可以看到,对于7*7*7*7*7*7,即7^6,与49*49*49,即49^3,结果是一样的,我们在可接受的范围内合并了底数,又优化了指数,这样我们不停的进行循环合并,就可以成功的写出快速幂算法。 如果指数是奇数,那就在偶数算法的基础上,把多余的一个数跳出来,剩下的与偶数算法一样,所以,这里多了一个奇偶判断。

 1 //base是底数,index是指数,mode是取模数,result是记录结果。
 2 typedef long long ll;
 3 ll Mode(ll base, ll index, ll mode)
 4 {
 5     ll result = 1;
 6     while(index)
 7     {
 8         if(index & 1)
 9         {
10             result = (result * base) % mode;
11             index--;
12         }
13         index >>= 1;
14         base = (base * base) % mode;
15     }
16     return result;
17 }

这就是快速幂算法。

作者:回首不知身是客