华师一附中OI组

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 2317|回复: 2
打印 上一主题 下一主题

精简的快速幂算法

[复制链接]

61

主题

147

帖子

563

积分

超级版主

Rank: 8Rank: 8

积分
563
跳转到指定楼层
楼主
发表于 2014-11-1 14:43:03 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
求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. }
复制代码

回复

使用道具 举报

61

主题

147

帖子

563

积分

超级版主

Rank: 8Rank: 8

积分
563
沙发
 楼主| 发表于 2014-11-1 15:04:53 | 只看该作者
还有一个快速算法比这个好理解,用递归实现:
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。


回复 支持 反对

使用道具 举报

738

主题

1485

帖子

5422

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5422
板凳
发表于 2020-7-24 11:45:52 | 只看该作者
联赛中多次考到快速幂,比如:NOIP2013转圈游戏,NOIP2000麦森数。
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|服务支持:DZ动力|华师一附中OI组  

GMT+8, 2024-12-25 15:11 , Processed in 0.108236 second(s), 23 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表