如何有效地计算 2 的大幂次？

Question

我正在尝试为 0 < n ≤ 10⁹ 计算

的值

re=(2^n)%1000000007

我写了这段代码：

int main()
{
    int n,i,re=1;
    scanf("%d",&n);
    for(i=0; n>i; i++) re=(2*re)%1000000007;
    printf("%d",re);
}

当 n 为 10⁹ 时，我的代码耗时过长。

我怎样做才能让它更快？

Answer 1

您可以遵循二进制求幂，类似于

#define MOD 1000000007

long long fastExp(int b, int e) {
    long long r=1;
    while(e>0) {
       if(e&1) r=(r*b)%MOD;
       b=(b*b)%MOD;
       e/=2;
    }
    return r%MOD;
}

这样称呼它fastExp(2,n)。

好吧，复杂性非常简单，因为它执行 log2(n) 操作，因此这比您的 O(n) 解决方案更好。

作为对您的解决方案获得 TLE 的原因的解释。 SPOJ等可用的在线判断通常需要1秒才能完成10^8循环操作。在这里，当您将 n=10^9 作为输入时，您可以做更多的事情。

Answer 2

你可以在 n 的对数时间内完成，计算能力更快。

#include <stdio.h>
#include <stdint.h>

const int kMod = 1000000007;

int Pow(int b, int p) {
    if (p == 0) return 1;
    int x = Pow(b, p >> 1);
    return ((((int64_t)x * x) % kMod) * (p & 1? b : 1)) % kMod;
}

int main()
{
    int n;
    scanf("%d", &n);
    //for(i=0; n>i; i++) re=(2*re)%1000000007;
    int re = Pow(2, n);
    printf("%d\n", re);
    return 0;
}

例如2⁵表示计算x = 2²和x * x * 2。

Answer 3

如果n小于30，结果是1 << n，否则你可以计算1 << 30并让你的for循环从31。如果检查 if (re > 1000000007) 并减去 1000000007（因为 re 在乘以 2，它比2*1000000007小，所以减去1000000007就够了）：

int foo(int n)
{
    if (n < 30) return 1 << n;
    int re = (1 << 30) % 1000000007;
    for(int i=31; n>i; i++)
    {
        re <<= 1;
        if (re > 1000000007) re -= 1000000007;
    }
    return re;
}

完整程序：https://ideone.com/0FRcaf

如何有效地计算 2 的大幂次？

How to efficiently compute large powers of 2?

c

performance

exponentiation

integer-arithmetic