前言：
如今我们对“取模运算法则”可能比较关心，姐妹们都想要剖析一些“取模运算法则”的相关知识。那么小编在网上汇集了一些关于“取模运算法则””的相关资讯，希望朋友们能喜欢，各位老铁们一起来了解一下吧！抛出问题
请设计一个算法求x的y次幂模z的结果：(x ^ y) % z
x、y、z都是整数z ≠ 0, y ≥ 0x、y的绝对值可能很大，比如(1234 ^ 4567) % 30
思考
由于x、y的绝对值可能很大，x ^ y的结果可能会溢出。所以先求x ^ y，再对z取模，显然是不现实的。
这里要借助模运算的一条运算规则
(a * b) % p = ((a % p) * (b % p)) % p
根据上面的推导，就可以很容易写出代码实现
递归实现
int powMod(int x, int y, int z) { if (y == 0) return 1 % z; int half = powMod(x, y >> 1, z); half = (half * half) % z; if ((y & 1) == 0) { // y是偶数 return half; } else { // y是奇数 return (half * (x % z)) % z; }}非递归实现int powMod(int x, int y, int z) { int result = 1 % z; x %= z; while (y != 0) { if ((y & 1) == 1) { result = (result * x) % z; } x = (x * x) % z; y >>= 1; } return result;}测试用例// 4powMod(1234, 4567, 30);// 699powMod(123, 456, 789);
如果你特别希望我写点哪方面的算法内容，也可以留言建议~
版权声明：
本站文章均来自互联网搜集，如有侵犯您的权益，请联系我们删除，谢谢。
标签： #取模运算法则 #大整数快速模运算算法与实现研究
