我正在尝试在 C 程序中计算以下数字:
result = (3 * pow(2,500000000) - 2 ) % 1000000000
2 的幂太大,无法正确处理 => 我的印象是,我可以使用模数将计算分成多个步骤,以减少结果大小。有人有这样做的策略吗?还有其他想法吗?
提前感谢
Manu
最简单的方法是通过在每一步中重复平方减少模数来求幂。
unsigned long long mod_pow(unsigned long long base, unsigned long long exponent, unsigned long long modulus)
{
if (exponent == 0) return 1;
unsigned long long aux = 1;
while(exponent > 1) {
if (exponent % 2 != 0) {
aux *= base;
aux %= modulus;
}
base *= base;
base %= modulus;
exponent /= 2;
}
return (base*aux) % modulus;
}
然后你可以用它来计算
result = (3*mod_pow(2,500000000,1000000000) - 2) % 1000000000;
该函数假设模数的平方不超过 64 位范围。对于较大的模数,事情会更加复杂。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)