华师一附中OI组

标题: 精简的快速幂算法 [打印本页]
作者: diggersun    时间: 2014-11-1 14:43
标题: 精简的快速幂算法
求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    时间: 2014-11-1 15:04
还有一个快速算法比这个好理解，用递归实现：
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    时间: 2020-7-24 11:45
联赛中多次考到快速幂，比如：NOIP2013转圈游戏，NOIP2000麦森数。



欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2