本文介绍了计算 2 模数的大幂的最快方法是什么的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着跟版网的小编来一起学习吧！
问题描述
限时送ChatGPT账号..
对于 1 <= N <= 1000000000，我需要计算 2N mod 1000000007，它一定非常快！
我目前的做法是:
For 1 <= N <= 1000000000, I need to compute 2N mod 1000000007, and it must be really fast!
My current approach is:
ull power_of_2_mod(ull n) {
ull result = 1;
if (n <= 63) {
result <<= n;
result = result % 1000000007;
}
else {
ull one = 1;
one <<= 63;
while (n > 63) {
result = ((result % 1000000007) * (one % 1000000007)) % 1000000007;
n -= 63;
}
for (int i = 1; i <= n; ++i) {
result = (result * 2) % 1000000007;
}
}
return result;
}
但它似乎不够快.有什么想法吗?
but it doesn't seem to be fast enough. Any idea?
推荐答案
这样会更快(C 代码):
This will be faster (code in C):
typedef unsigned long long uint64;
uint64 PowMod(uint64 x, uint64 e, uint64 mod)
{
uint64 res;
if (e == 0)
{
res = 1;
}
else if (e == 1)
{
res = x;
}
else
{
res = PowMod(x, e / 2, mod);
res = res * res % mod;
if (e % 2)
res = res * x % mod;
}
return res;
}
这篇关于计算 2 模数的大幂的最快方法是什么的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持跟版网！
本站部分内容来源互联网,如果有图片或者内容侵犯了您的权益，请联系我们，我们会在确认后第一时间进行删除！