我是靠谱客的博主 大意奇异果,这篇文章主要介绍快速幂取模,现在分享给大家,希望可以做个参考。

问题定义:

数论中经常出现的一个问题是对一个数的幂取模,也称为模取幂,即求a^b mod n。如果计算量较小,可以直接计算出a^b的值,再作模n运算。但是如果a和b的值都非常大,a^b的值用计算机难以表示,或者即使可以用大数运算的方式用计算机表示,也会因为耗时过长难以应用。基于模运算的基本性质,可以设计出一种算法,快速求解这一问题。这种方法为“快速幂取模”,也称为“反复平方法“。

算法原理:

算法基础在于模运算的基本性质
(a+(*)b)%n=(a%n+(*)b%n)%n
(a-b)%n=(a%n-b%n+n)%n
(a*b)%n=(a%n*b%n)%n

算法实现的原理是:

算法1:利用公式a*b%c=((a%c)*b)%c,这样每一步都进行这种处理,这就解决了a^b可能太大存不下的问题,但这个算法的时间复杂度依然没有得到优化
代码如下:

复制代码
1
2
3
4
5
6
7
8
9
10
int modexp_simple(int a,int b,int n) { int ret = 1; while (b--) { ret = a * ret % n; } return ret; }

算法2:另一种算法利用了二分的思想,可以达到O(logn)。
可以把b按二进制展开为:b = p(n)*2^n + p(n-1)*2^(n-1) +…+ p(1)*2 + p(0)
其中p(i) (0<=i<=n)为 0 或 1

这样 a^b = a^ (p(n)*2^n + p(n-1)*2^(n-1) +…+ p(1)*2 + p(0))
= a^(p(n)2^n) a^(p(n-1)2^(n-1)) …* a^(p(1)2) a^p(0)
对于p(i)=0的情况, a^(p(i) * 2^(i-1) ) = a^0 = 1,不用处理
我们要考虑的仅仅是p(i)=1的情况
化简:a^(2^i) = a^(2^(i-1) * 2) = ( a^( p(i) * 2^(i-1) ) )^2
(这里很重要!!具体请参阅秦九韶算法:http://baike.baidu.com/view/1431260.htm)
利用这一点,我们可以递推地算出所有的a^(2^i)
当然由算法1的结论,我们加上取模运算:
a^(2^i)%c = ( (a^(2^(i-1))%c) * a^(2^(i-1))) %c
于是再把所有满足p(i)=1的a^(2^i)%c按照算法1乘起来再%c就是结果, 即二进制扫描从最高位一直扫描到最低位

实例代码:递归

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//计算a^bmodn int modexp_recursion(int a,int b,int n) { int t = 1; if (b == 0) return 1; if (b == 1) return a%n; t = modexp_recursion(a, b>>1, n); t = t*t % n; if (b&0x1) { t = t*a % n; } return t; }

实例代码2:非递归优化

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream> using namespace std; //计算a^bmodn int modexp(int a,int b,int n) { int ret=1; int tmp=a; while(b) { //基数存在 if(b&0x1) ret=ret*tmp%n; tmp=tmp*tmp%n; b>>=1; } return ret; } int main() { cout<<modexp(2,10,3)<<endl; return 0; }

最后

以上就是大意奇异果最近收集整理的关于快速幂取模的全部内容,更多相关快速幂取模内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(76)

评论列表共有 0 条评论

立即
投稿
返回
顶部