어떻게 2의 큰 힘을 효율적으로 계산합니까? 내가 <code>0 < n ≤ 10⁹</code>를 들어, 계산하기 위해 노력하고있어

Question

,이 코드 작성

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의 대수 시간으로 수행 할 수 있습니다. n가 30보다 작은 경우, 예를 들어

#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 2

이 fastExp(2,n) 같은 같은

#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; 
} 

전화를 할 것이다 이진 지수를 따를 수 있습니다.

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