Вычислить (a^b)% c, где 0 <= a, b, c <= 10^18

Question

Как рассчитать (a^b) % c, где 0 <= a, b, c <= 10^18. Здесь (a^b) означает a на питание b, а не a xor b.

Мой текущий код проблемы:

unsigned long long bigMod(unsigned long long b, 
          unsigned long long p, 
          unsigned long long m){ 
    if(b == 1) return b; 
    if(p == 0) return 1; 
    if(p == 1) return b; 

    if(p % 2 == 0){ 
     unsigned long long temp = bigMod(b, p/2ll, m); 
     return ((temp) * (temp))% m; 
    }else return (b * bigMod(b, p-1, m)) % m; 
} 

Для этого входа:

a = 12345 b = 123456789 and c = 123456789

ожидаемый результат должен быть:

59212459031520 

Answer 1

Я использую этот код в C++:

long long power(long long a, long long b, long long c) 
{ 
    if (b==0) 
    { 
     return 1; 
    } 

    if (b % 2 == 0) 
    { 
     long long w = power(a, b/2, c); 
     return (w*w) % c; 
    } 
    else 
    { 
     int w = power(a, b-1, c); 
     return (a*w) % c; 
    } 
} 

Он имеет логарифмическую сложность.

Answer 2

У вас возникла проблема с temp * temp (long long overflow). Вы можете опустить эту проблему, используя алгоритм быстрой моды, чтобы умножить их mod m. Здесь Вы рабочий код:

unsigned long long bigMultiply(unsigned long long b,unsigned long long p, unsigned long long m) 
{ 
    if(p == 0)return b; 
    if(p%2 == 0) 
    { 
    unsigned long long temp = bigMultiply(b,p/2ll,m); 
    return ((temp)+(temp))%m; 
    } 
    else 
    return (b + bigMultiply(b,p-1,m))%m; 
}  
unsigned long long bigMod(unsigned long long b,unsigned long long p, unsigned long long m) 
{ 

    if(b == 1) 
    return b; 
    if(p == 0)return 1; 
    if(p == 1)return b; 
    if(p%2 == 0) 
    { 
    unsigned ll temp = bigMod(b,p/2ll,m); 
    return bigMultiply(temp,temp,m); 
    } 
    else 
    return (b * bigMod(b,p-1,m))%m; 
}