빠른 거듭제곱과 Modular Inverse

일반적으로 특정 수를 $N$ 제곱하는데 걸리는 시간은 $O(N)$ 이지만, 간단한 수학으로 이를 $O(\log N)$에 마칠 수 있다. 이는 거듭제곱 하고자 하는 수를 이진수로 보고, binary lifting 하는 것이라고 보면 된다.

예를 들어, $a$의 $13$ 제곱을 하고자 한다면, 이는 이진수로 $1101_{(2)}$이므로,

• $1$ 제곱 한 수
• $4$ 제곱 한 수
• $8$ 제곱 한 수

를 모두 곱하면 된다. $2^n$ 제곱 한 수는 같은 수를 두번 곱함으로써 빠르게 구해진다. ($8$제곱한 수는 $4$제곱한 수를 두번 곱하면 된다)

따라서 아래와 같은 알고리즘 작성이 가능하다. $a^p$를 구하는 알고리즘이다. 기하급수적으로 커지므로, MOD로 나머지만 들고다니도록 많이 구현하는 편.

ll fpow(ll a, ll p) {
    ll res = 1LL;
    while (p) {
        if (p & 1LL) res = res * a % MOD;
        a = a * a % MOD;
        p >>= 1LL;
    }
    return res;
}

Modular Inverse

오일러 공식을 사용하면, $p$가 소수일 때, $n^{-1} = n^{p-2}$가 성립한다. 일반적으로는 실수오차 때문에 짜증나는 분수를 신나게 계산할 수 있다. 앳코더에서 자주 사용한다. 일반적으로 주어지는 소수 $p$가 크기 때문에, 위의 빠른 거듭제곱 공식과 같이 사용해야 한다.

아래 백준 문제에 왜 이 방식을 쓰는지 자세히 설명되어 있다.

• Sum 문제: https://www.acmicpc.net/problem/13172

ll getInv(ll v) {
    return fastPow(v, MOD - 2);
}

Time Complexity

• $O(\log N)$. 일종의 Binary Lifting 이다.