큰 지수를 사용하여 (a^b)%MOD 계산

이 코딩 과제에서 작업은 pow( a, b)%MOD, 여기서 지수 b는 매우 클 수 있습니다. 기존의 log(b) 시간 복잡도 방법은 더 작은 값에 적합하지만 b가 C의 long long 데이터 유형의 용량을 초과하면 실용적이지 않습니다.

그러나 보다 효율적인 접근 방식에는 오일러의 토션트 함수를 활용하는 것이 포함됩니다. Φ(MOD). 오일러의 정리는 a^ψ(MOD)=1(mod MOD)라고 말합니다. 이는 a의 거듭제곱이 a^(b % Φ(MOD))로 크게 감소할 수 있음을 의미합니다.

Φ(MOD)를 계산하는 것은 그 자체로 중요한 작업이지만 정수 인수분해 방법을 사용하여 달성할 수 있습니다. . 일단 계산되면 지수 b를 b % ψ(MOD)로 대체하여 계산 시간을 획기적으로 줄일 수 있습니다.

추가 개선

2008년 Schramm은 Φ (b)는 i가 1에서 b까지인 경우 gcd(b, i)의 이산 푸리에 변환으로부터 얻을 수 있습니다. 이렇게 하면 명시적 인수분해가 필요하지 않습니다.

또한 Carmichael 함수 λ(MOD)를 사용하여 특히 a와 MOD가 공통 인수를 공유하는 경우 정답을 얻을 수 있습니다.

코드 구현

다음 코드 조각은 C의 예입니다. :

#include 
#include 

using namespace std;

typedef long long ll;

ll gcd(ll a, ll b) { return (b == 0) ? a : gcd(b, a % b); }

ll pmod(ll a, ll b, ll mod) {
    if (b == 0) return 1;
    if (b % 2 == 1) {
        return (a * pmod(a, b - 1, mod)) % mod;
    } else {
        ll tmp = pmod(a, b / 2, mod);
        return (tmp * tmp) % mod;
    }
}

int main() {
    ll a, b, mod;
    cin >> a >> b >> mod;
    cout