빠른 모듈러 지수에서 오버플로를 피하는 방법

Question

저는 모듈러 지수를 필요로하는 SPOJ에 관한 질문을 풀려고합니다. 내가 (2^249999999997)%999999999989을 계산할 때 다음과 같은 C 코드

long long modpow(long long a,long long b,long long mod) 
{ 
    long long product,pseq; 
    product=1 
    pseq=a%mod; 
    while(b>0) 
    { 
     if(b&1) 
      product=(product*pseq)%mod; 
     pseq=(pseq*pseq)%mod; 
     b>>=1 
    } 
    return product; 
} 

을 문제가 사용하고,이 때문에 오버 플로우의 0 답변을 제공합니다. 오버플로를 피하려면 어떻게해야합니까?

Answer 1

Untestet,하지만 당신은 아이디어를 얻을. 2*mod이 최대 표현 가능 범위 인 long long 값보다 작고 a, b 및 mod이 양수인 경우에만 작동해야합니다.

long long modpow(long long a,long long b,long long mod) 
{ 
    long long product,pseq; 
    product=1; 
    pseq=a%mod; 
    while(b>0) 
    { 
     if(b&1) 
      product=modmult(product,pseq,mod); 
     pseq=modmult(pseq,pseq,mod); 
     b>>=1; 
    } 
    return product; 
} 

long long modmult(long long a,long long b,long long mod) 
{ 
    if (a == 0 || b < mod/a) 
     return (a*b)%mod; 
    long long sum; 
    sum = 0; 
    while(b>0) 
    { 
     if(b&1) 
      sum = (sum + a) % mod; 
     a = (2*a) % mod; 
     b>>=1; 
    } 
    return sum; 
} 

Answer 2

당신은 부호 오래 오래 대신 긴 긴 의를 사용할 수 있습니다, 그것은 당신이 그 범위 18,446,744,073,709,551,615에 0보다 높은 값으로 재생하는 데 도움이 될 것입니다.

Answer 3

추가 제안 사항 중 하나는 999999999989가 소수임을 사용하는 것입니다. (a^n) = a % n (n은 소수) 관계를 사용하면 u가 작업을 단순화 할 수 있습니다.