【问题】
计算a**b%c的值。
其中,"**"代表幂(Python中就是这样表示的);"%"代表取模运算。
【分析】
首先由模运算的性质,可以得到下面的公式:
(a*b) % c = (a%c) * b % c 【公式一】
将【公式一】继续展开,可得下面的公式:
(a*b) % c = (a%c) * b % c = (b%c) * (a%c) % c = (a%c) * (b%c) % c 【公式二】
下面是几种解决方法: 【方法1】利用公式一,使用递归方法计算。
#include #include // calculate a**b%c int fun(int a, int b, int c) { assert(a && (b>=0) && c); if (0==b) { return 1; } else { return fun(a, b-1, c)*a%c; } } int main() { int a, b, c; while (3==scanf("%d%d%d",&a,&b,&c)) { printf("%d\n",fun(a,b,c));// calculate a**b%c } return 0; } 不难看出此方法的缺点是当b越大的时候需要递归的次数就越多,因此就可能会发生stack overflow的错误。所以,此方法非常简单但只适用于b比较小的情况。VS2008下测试,当递归到4624次时发生stack overflow。
【方法2】利用公式二,使用递归方法计算。
想办法在方法1的基础上减少递归次数,发现利用公式二可以做到。
(a*b) % c = (a%c) * (b%c) % c 【公式二】
当b是奇数的时候,f(b) = f(b-1) * (a % c) % c = a * f(b-1) % c
当b是偶数的时候,f(b) = f(b/2) * f(b/2) % c #include #include #include // calculate a**b%c int fun(int a, int b, int c) { assert(a && (b>=0) && c); if (0==b) { return 1; } else { return (1==(b&1)) ? a*fun(a, b-1, c)%c : fun(a, b/2, c)*fun(a, b/2, c)%c; } } int main() { int a, b, c; clock_t beg, end; while (3==scanf("%d%d%d",&a,&b,&c)) { beg=clock(); printf("%d\n",fun(a,b,c));// calculate a**b%c end=clock(); printf("time used: %.2lf\n",double(end-beg)/CLOCKS_PER_SEC); } return 0; } VS2008测试:a=3; b=2147483647;(取int型的最大值) c=1000时,需要约225s可计算出结果为787。
此方法减少了递归次数,在所能表示的类型里可以防止栈溢出的问题(下面可推证),但是发现运算效率还是太慢,对代码进行检查可以发现问题出在下面这行代码中:
fun(a, b/2, c)*fun(a, b/2, c)%c;
这种写法会导致递归调用函数的次数可能达到2*lb(b),虽然递归深度要远小于方法1,但递归次数要远远大于方法1(可以设置一个局部静态变量显示),所以效率很低。解决方法可以先用一个临时变量来保存函数调用的返回值,优化方法如下:
#include #include #include // calculate a**b%c int fun(int a, int b, int c) { assert(a && (b>=0) && c); if (0==b) { return 1; } else { //return (1==(b&1)) ? a*fun(a, b-1, c)%c : fun(a, b/2, c)*fun(a, b/2, c)%c; if (b&1)// odd { return a*fun(a, b-1, c)%c; } else// even { int tmp=fun(a, b/2, c);// note here! return tmp*tmp%c; } } } int main() { int a, b, c; clock_t beg, end; while (3==scanf("%d%d%d",&a,&b,&c)) { beg=clock(); printf("%d\n",fun(a,b,c));// calculate a**b%c end=clock(); printf("time used: %.2lf\n",double(end-beg)/CLOCKS_PER_SEC); } return 0; } 用上述同样的数据测试,发现计算所用时间几乎为0.00s,效率得到很大提高。
思考:虽然这种方法减少了递归次数,但是当b特别大的时候是否还会出现stack overflow的情况。
测试:将b改为__int64或long long类型,看是否会发生stack overflow并计算时间。
可以粗略地分析出:在32位平台上用这种方法可以计算出b最大为2^4624时的结果而不会发生栈溢出。 #include #include #include // calculate a**b%c int fun(int a, __int64 b, int c) { assert(a && (b>=0) && c); // 打印出递归次数 /*static int itime=0; printf("%d\n",itime++);*/ if (0==b) { return 1; } else { if (b&1)// odd { return a*fun(a, b-1, c)%c; } else// even { int tmp=fun(a, b/2, c);// note here! return tmp*tmp%c; } } } int main() { int a, c; __int64 b; clock_t beg,end; while (3==scanf("%d%I64d%d",&a,&b,&c)) { beg=clock(); printf("%d\n",fun(a,b,c));// calculate a**b%c end=clock(); printf("time used: %.2lf\n",double(end-beg)/CLOCKS_PER_SEC); } return 0; } 测试:a=3; b=9223372036854775807; c=1000; 输出187,用时几乎为0.00s。
【方法3】利用公式一,使用递推方法(非递归)计算。 #include #include #include // calculate a**b%c int fun(int a, int b, int c) { assert(a && (b>=0) && c); int res=1; while (b>0) { res*=a; res%=c; --b; } return res; } int main() { int a, b, c; clock_t beg,end; while (3==scanf("%d%d%d",&a,&b,&c)) { beg=clock(); printf("%d\n",fun(a,b,c));// calculate a**b%c end=clock(); printf("time used: %.2lf\n",double(end-beg)/CLOCKS_PER_SEC); } return 0; } 测试:a=3; b=2147483647;(取int型的最大值) c=1000时,用时约37.02s可计算出结果为787。
因为此方法需要循环b次,时间复杂度为O(b),效率比较低,但是优点是不会发生stack overflow。
【方法4】利用公式二,使用递推方法(非递归)计算。 #include #include #include // calculate a**b%c int fun(int a, int b, int c) { assert(a && (b>=0) && c); int res=1; while (b) { if (b&1)// odd { res=res*a%c; --b; } else// even { a=a*a%c; b>>=1; } } return res; } int main() { int a, b, c; clock_t beg, end; while (3==scanf("%d%d%d",&a,&b,&c)) { beg=clock(); printf("%d\n",fun(a,b,c));// calculate a**b%c end=clock(); printf("time used: %.2lf\n",double(end-beg)/CLOCKS_PER_SEC); } return 0; } 测试:a=3; b=2147483647;(取int型的最大值) c=1000时,用时约0.00s可计算出结果为787。此方法最好的时间复杂度为O(lb(b)),且不会发生stack overflow。
【方法5】与方法4等价的另一种形式。
不对b进行减1或除以2,而将b表示为二进制数,通过判断二进制位上是0还是1来计算。这种方法的时间复杂度最小,即O(nbit),n是b的二进制表示的位数。比如:
b==8(dec.)==1000(bin.),用方法4需要循环2+1+1+0=4次;用方法3也需要循环4次。
b==7(dec.)==0111(bin.),用方法4需要循环2+2+1=5次;用方法3需要循环4次。
使用数组实现 : #include #include #include // calculate a**b%c int fun(int a, int b, int c) { assert(a && (b>=0) && c); int res=1, n=0;// n+1 is the length of b in binary int bit_b[32]={0}; while (b) { bit_b[n++]=(b%2); b>>=1; } for (int i=n-1; i>=0; --i) { res=res*res%c; if (bit_b[i]) { res=res*a%c; } } return res; } int main() { int a, b, c; clock_t beg, end; while (3==scanf("%d%d%d",&a,&b,&c)) { beg=clock(); printf("%d\n",fun(a,b,c));// calculate a**b%c end=clock(); printf("time used: %.2lfs\n",(double)(end-beg)/CLOCKS_PER_SEC); } return 0; } 使用bitset容器实现 : #include #include #include using std::bitset; // calculate a**b%c int fun(int a, int b, int c) { assert(a && (b>=0) && c); int res=1, n;// n+1 is the length of b in binary bitset bitvec_b(b); n=bitvec_b.size()-1; while (0==bitvec_b[n]) --n; for (int i=n; i>=0; --i) { res=res*res%c; if (bitvec_b[i]) { res=res*a%c; } } return res; } int main() { int a, b, c; while (3==scanf("%d%d%d",&a,&b,&c)) { printf("%d\n",fun(a,b,c));// calculate a**b%c } return 0; } 参考 :
发表评论
-
字符串类型转换
2012-07-06 09:51 7511. CString和char *转换 CString重 ... -
正则表达式
2012-07-06 09:44 499记得在做数据抓去的时候正则表达式写的很溜,几年不用现在都不 ... -
常用正则表达式
2012-07-06 09:37 639匹配中文字符的正则表达式: [u4e00-u9fa5] ... -
ASP.NET中Theme使用方法详解
2012-07-06 09:29 871ASP.NET开发技巧之Theme功能主要是有什么呢?那么 ... -
js动态生成表格
2012-07-05 20:44 670- 0; t *= 10, e--); for (; ... -
桌面组件开发学习笔记
2012-07-03 13:42 6031. 桌面组 ... -
桌面组件开发学习笔记
2012-07-03 12:17 6211. 桌面组 ... -
OpenScales入门教程:第二节 : 创建第一张地图
2012-07-02 10:13 1085你需要把第一 ... -
Alert提示框备用
2012-07-02 10:13 598Alert { /**通 ... -
遮罩的使用
2012-07-02 10:13 590有N个按钮又不想其导航栏出现烦人的滚动条。 解决方法 ... -
fxmq
2012-07-02 10:13 678Flex Message Queue (fxmq) (ba ... -
Flex remoteobject工作原理探讨
2012-07-01 09:34 651Flex访问远程服务都是通过AbstractService ... -
Cross-domain policy和/WEB-INF/flex/proxy-config.xml
2012-07-01 09:34 648从flash 7开始,不同域名的资源访问受到限制,比如a. ... -
Flex Socket编程
2012-07-01 09:34 711比较懒,比较少上csdn的,如果发现留言给我没有回复,望见 ... -
Flex与.net交互
2012-07-01 09:33 389方法一: 把Flex生成的SWF文件(在目录../h ... -
比较好的firefox中字符换行解决方法
2012-06-30 17:51 474在网页中经常碰到字符断行的问题,一般情况下只要设置了外层容 ... -
LINUX终端乱码解决方法
2012-06-30 17:51 600安装Linux时选择使用中文,当使用SSH、TELNET ... -
Ubuntu 9.10升级后 启动黑屏的解决方法
2012-06-30 17:51 1010安装完 9.10后,我 ...
相关推荐
行业-电子-模幂运算电路和系统及模幂运算方法的说明分析.rar
有限域F2 多项式的模幂运算 对指数进行二进制分解 结合位运算 加快运算速度
通过本实验,使学生切实掌握作为大多数公钥密码计算基础的“模逆”与“模幂”算法,并学会运用上述两个基本算法来实现诸如 RSA、ElGamal 等公钥密码的各主要需求和功能,最终对“一个公钥密码体制如何应用”形成一定...
按照平方乘算法和模重复平方法,分别计算ammodn。
在大部分公钥密码体制中,大数模幂运算一直是最重要的运算之一,它的实现速度 ...本文总结了一些经典的大数模幂运算算法,并对这些算法的有效使用 发表了一些看法,最后对其中的一些算法提出了改进。
封装好的扩展欧几里得、模幂运算及欧拉函数算法代码
大数运算包含加,减,乘,除,取模,幂运算,模幂运算。支持十进制运算,二进制运算;支持文件运算,键盘输入运算,若有需要,可提供实验报告
行业资料-电子功用-数据的防攻击方法及装置、RSA模幂运算方法、装置和电路
易语言大数幂模运算源码,大数幂模运算
常用的模幂算法实现方式,并且还有新的方法,算法速度很快,限个人使用。
单云服务器下的安全外包模幂运算.pdf
5.2 如何高效进行模幂运算本文对应的力扣题目:372.超级次方// 计算 a 的 k 次方然后与 base 求模的结果// 对因子求模// 这里有乘法,是潜在
在RSA密码体制中,加密和解密运算都是模指数运算。计算 可以通过c-1次模乘来实现,然而,如果c非常大,其效率会很低下。 著名的平方-乘可以把计算所需的模乘的次数降低。
加减乘除幂运算等等的告警运算算法。。可以解决数据溢出问题哦
利用自己定义的大数类型,使用加法链和蒙哥马利算法的混合算法极大的提高了幂运算和幂模运算的速度。
一种改进的针对滑动窗口模幂运算实现的密码数据Cache计时攻击
自己写得大数浮点数幂运算(c++实现),系poj acm 的problem:1001的实现
主要为大家详细介绍了C++使用string的大数快速模幂运算,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
模拟幂运算,可以求超出数据表示范围的较大幂值
的对传统BR算法的改进方法,能明显提高大数模幂乘运算的效率,从而大大减短加密解密的时间,提高加密解密的效率。