擅长:python、mysql、java
<p>如前所述,您的问题是对于大指数,存在整数溢出。在</p>
<p>要克服这一点,请记住模乘有这样的性质:</p>
<blockquote>
<p>(A * B) mod C = (A mod C * B mod C) mod C</p>
</blockquote>
<p>然后你就可以用快速求幂的方法实现“e到幂p模m”函数。
假设没有负幂:</p>
<pre><code>long long powmod(long long e, long long p, long long m){
if (p == 0){
return 1;
}
long long a = 1;
while (p > 1){
if (p % 2 == 0){
e = (e * e) % m;
p /= 2;
} else{
a = (a * e) % m;
e = (e * e) % m;
p = (p - 1) / 2;
}
}
return (a * e) % m;
}
</code></pre>
<p>请注意,余数是在每次乘法之后获得的,因此如果单个乘法不溢出(对于<code>1000000007</code>作为<code>m</code>和{<cd3>}),则不会发生溢出。在</p>