大佬教程收集整理的这篇文章主要介绍了算法C/C++:用n和d 32或64位整数计算(2 ^ n)%d的最快方法,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
问题是即使使用多精度库也不可能将2 ^ n存储在内存中,但也可能存在使用32或64位整数来计算(2 ^ n)%d的技巧.
非常感谢你.
这个想法不是计算2 ^ n.而是在上电时减少模数d. That keeps the number small.
将方法与Exponentiation by Squaring组合,您只能在O(log(n))步骤中计算(2 ^ n)%d.
这里有一个小例子:2 ^ 130%123 = 40
2^1 % 123 = 2 2^2 % 123 = 2^2 % 123 = 4 2^4 % 123 = 4^2 % 123 = 16 2^8 % 123 = 16^2 % 123 = 10 2^16 % 123 = 10^2 % 123 = 100 2^32 % 123 = 100^2 % 123 = 37 2^65 % 123 = 37^2 * 2 % 123 = 32 2^130 % 123 = 32^2 % 123 = 40
以上是大佬教程为你收集整理的算法C/C++:用n和d 32或64位整数计算(2 ^ n)%d的最快方法全部内容,希望文章能够帮你解决算法C/C++:用n和d 32或64位整数计算(2 ^ n)%d的最快方法所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。