快速幂取模_C++
2018-06-17 23:57:03来源:未知 阅读 ()
一、题目背景
已知底数a,指数b,取模值mo
求ans = ab % mo
二、朴素算法(已知可跳过)
ans = 1,循环从 i 到 b ,每次将 ans = ans * a % mo
时间复杂度O(b)
1 void power(int a,int b,int mo) 2 { 3 int i; 4 ans=1; 5 for (i=1;i<=b;i++) 6 { 7 ans*=a; 8 ans%=mo; 9 } 10 }
三、快速幂
先讨论无需取模的
当b为偶数时:ab=a(b/2)*2=(a2)b/2
当b为奇数时:ab=a*ab-1=a*(a2)(b-1)/2
如 28=(22)4 27=2*(22)3
所以,我们可以如此迭代下去
210=(22)5=(22)*[(22)2]2
① ② ③
指数为10 是一个偶数,则底数2平方,指数变为一半 [ ①→② ]
指数为5 是一个奇数,则先将底数提出作为系数(22),此时指数为4 是一个偶数,则底数22再平方,指数再变为一半 [ ②→③ ]
归纳总结得到:
当指数大于1时,若为 偶数 则将指数除以2,底数平方
若为 奇数 则先提出一个为底数的系数(可直接把该系数乘进ans中),所以指数减1,然后再按照 偶数 的办法做
不断迭代下去,当指数为1时,则直接得出答案
最后只要将每次相乘时取模即可,时间复杂度O(log2b)
1 inline int mi(int a,int b) 2 { 3 int ans=1; 4 a%=mo; 5 while (b) 6 { 7 if (b&1) ans=ans*a%mo; 8 b>>=1; 9 a=a*a%mo; 10 } 11 return ans; 12 }
(代码更新时间2016年11月7日17:20:54)
版权所有,转载请联系作者,违者必究
QQ:740929894
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:TCP通信三次握手的过程
- C++ 转换函数搭配友元函数 2020-06-10
- C++ 自动转换和强制类型转换(用户自定义类类型) 2020-06-10
- C++ rand函数 2020-06-10
- C++ 友元函数 2020-06-10
- C++ 运算符重载 2020-06-10
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash