2の大出力を効率的に計算する方法は？私は計算しようとしている

Question

は、0 < n ≤ 10⁹ため、

re=(2^n)%1000000007 

の値は、私はこのコードを書いた：nが10⁹とき

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

、私のコードは、時間がかかりすぎます。

私はそれをより速くするために何ができますか？

Answer 1

電力計算をより速く計算することによって、対数時間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; 
} 

nが30よりも小さい場合、2 は、x = 2 及びX *、X * 2

Answer 2

あなたは

#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のように利用できるオンライン審査員は通常、ループ操作10^8を行うのに1秒かかります。ここでは、n=10^9を入力すると、それ以上のことができます。

Answer 3

の計算を意味し、結果は1 << nあり、そうでなければ、算出することができます。 1 << 30とforループの開始時刻を31にします。あなたがif (re > 1000000007)をチェックして、1000000007を引く場合は、高価な%操作を取り除くことができます（reが2を掛ける前に1000000007よりも小さいので、それはそう1000000007を差し引く、十分2*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