精简的快速幂算法

diggersun

求3^10经典小程序
计算3^10没有必要3*3*3*3*3*3*3*3*3*3，另外还有很多的简便算法。比如这种

3*3=9   得到3^2
9*9=81 得到3^4
81*81=6561  得到3^8
6561*9=59049  得到3^10
为什么可以这样呢?你看10化成二进制是1010，从右看到左
第0位是0 不用计入答案，准备第一位3*3=9
第1位是1 9要计入答案，答案得9，准备第2位9*9=81
第2位是0 81不用计入答案，准备第3位81*81=6561
第3位是1 6561要计入答案 ，答案是9*6561=59049，不用准备第4位了，结束了。

或者先来个简单的，我们来计算3^8。8化成二进制是1000，
第0位是0 不用计入答案，准备第一位3*3=9
第1位是0 不用计入答案，准备第2位9*9=81
第2位是0 不用计入答案，准备第3位81*81=6561

第3位是1 计入答案，那就是6561，后面没有了。

8 和10 相比，化成二进制就是第1位0和1的区别，第1位对应的数数9，所以3^8 和 3^10相比少乘了一个9。
总结算法，在化成二进制的时候，若这一位是1，要把当前值计入答案，若是0，则不用计入。每次化的时候i减半，t就自乘一次，相当于说(3^i)^2=(3^(i/2))^2。

1. #include <iostream>
   
2. using namespace std;
   
3. long long  s,t;
   
4. int i,j;
   
5. int main()
   
6. {
   
7.     i=10;
   
8.     s=1;
   
9.     t=3;
   
10.     while (i>0)
    
11.     {
    
12.         if (i%2!=0) s=s*t;
    
13.         i=i/2;
    
14.         t=t*t;
    
15.     }
    
16.     cout<<s<<endl;
    
17.     return 0;
    
18. }
    

复制代码

diggersun

还有一个快速算法比这个好理解，用递归实现：
3^10=(3^5)^2
3^5=(3^2)^2*3  因为5%2==1，多乘一个
3^2=(3^1)^2
所以就是说
1、3^1=3
2、若x是奇数则3^x=(3^(x/2))^2*3，若x是偶数则3^x=(3^(x/2))^2。

1. long long ksm(int i)
   
2. {
   
3.         if (i==1) return 3;
   
4.         long long t=ksm(i/2);
   
5.         if (i%2==0) return t*t;
   
6.         else return t*t*3;
   
7. }

复制代码

还有一个思路就是 ：
1、3^1=3
2、若x是奇数则3^x=(3^(x-1))*3，若x是偶数则3^x=(3^(x/2))^2。

admin

联赛中多次考到快速幂，比如：NOIP2013转圈游戏，NOIP2000麦森数。