$p$를 법으로 하는 팩토리얼¶

이항 계수 공식에서 볼 수 있는 것처럼 분자와 분모 모두에 팩토리얼이 들어 있는 복잡한 식을 어떤 소수 $p$를 법으로 하여 다루어야 하는 경우가 있습니다. 여기서는 $p$가 비교적 작은 경우를 다룹니다. 이 문제는 팩토리얼이 분수의 분자와 분모 모두에 나타날 때에만 의미가 있습니다. 그렇지 않으면 $p!$ 및 그 이후의 항은 0이 됩니다. 하지만 분수에서는 $p$의 인수가 약분될 수 있으므로, 결과로 얻는 식은 $p$를 법으로 하여 0이 아니게 됩니다.

따라서 형식적으로 과제는 다음과 같습니다. 팩토리얼에 나타나는 $p$의 배수 인수를 모두 고려하지 않고 $n! \bmod p$를 계산하려고 합니다. $n!$의 소인수분해를 적은 다음, 인수 $p$를 모두 제거하고, 그 곱을 $p$를 법으로 계산한다고 생각해 보십시오. 이 변형된 팩토리얼을 $n!_{\%p}$로 나타내겠습니다. 예를 들어 $7!_{\%p} \equiv 1 \cdot 2 \cdot \underbrace{1}_{3} \cdot 4 \cdot 5 \underbrace{2}_{6} \cdot 7 \equiv 2 \bmod 3$입니다.

이 변형된 팩토리얼을 효율적으로 계산하는 방법을 익히면 다양한 조합 공식(예를 들어 이항 계수)의 값을 빠르게 계산할 수 있습니다.

알고리즘¶

이 변형된 팩토리얼을 명시적으로 적어 봅시다.

$$\begin{eqnarray} n!_{\%p} &=& 1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p-2) \cdot (p-1) \cdot \underbrace{1}_{p} \cdot (p+1) \cdot (p+2) \cdot \ldots \cdot (2p-1) \cdot \underbrace{2}_{2p} \\ & &\quad \cdot (2p+1) \cdot \ldots \cdot (p^2-1) \cdot \underbrace{1}_{p^2} \cdot (p^2 +1) \cdot \ldots \cdot n \pmod{p} \\\ &=& 1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p-2) \cdot (p-1) \cdot \underbrace{1}_{p} \cdot 1 \cdot 2 \cdot \ldots \cdot (p-1) \cdot \underbrace{2}_{2p} \cdot 1 \cdot 2 \\ & &\quad \cdot \ldots \cdot (p-1) \cdot \underbrace{1}_{p^2} \cdot 1 \cdot 2 \cdot \ldots \cdot (n \bmod p) \pmod{p} \end{eqnarray}$$

팩토리얼이 마지막 블록을 제외하고 같은 길이의 여러 블록으로 나뉜다는 것을 분명히 알 수 있습니다.

$$\begin{eqnarray} n!_{\%p}&=& \underbrace{1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p-2) \cdot (p-1) \cdot 1}_{1\text{st}} \cdot \underbrace{1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p-2) \cdot (p-1) \cdot 2}_{2\text{nd}} \cdot \ldots \\\ & & \cdot \underbrace{1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p-2) \cdot (p-1) \cdot 1}_{p\text{th}} \cdot \ldots \cdot \quad \underbrace{1 \cdot 2 \cdot \cdot \ldots \cdot (n \bmod p)}_{\text{tail}} \pmod{p}. \end{eqnarray}$$

블록의 주요 부분은 계산하기 쉽습니다. 그 값은 단순히 $(p-1)!\ \mathrm{mod}\ p$입니다. 이 값은 프로그램으로 계산할 수도 있고, 모든 소수 $p$에 대해 $(p-1)! \bmod p = -1$이라는 윌슨 정리를 그대로 적용할 수도 있습니다.

이러한 블록은 정확히 $\lfloor \frac{n}{p} \rfloor$개이므로, $-1$을 $\lfloor \frac{n}{p} \rfloor$제곱해야 합니다. 이는 이진 거듭제곱을 사용하여 로그 시간에 할 수 있습니다. 하지만 결과가 $-1$과 $1$을 번갈아 오간다는 점에 주목하면, 지수의 홀짝성만 확인하여 홀수이면 $-1$을 곱하기만 하면 됩니다. 또한 곱셈 대신 현재 결과를 $p$에서 빼기만 해도 됩니다.

마지막 부분 블록의 값은 $O(p)$에 따로 계산할 수 있습니다.

이제 각 블록의 마지막 원소만 남습니다. 이미 처리한 원소를 가리면 다음과 같은 패턴을 볼 수 있습니다.

$$n!_{\%p} = \underbrace{ \ldots \cdot 1 } \cdot \underbrace{ \ldots \cdot 2} \cdot \ldots \cdot \underbrace{ \ldots \cdot (p-1)} \cdot \underbrace{ \ldots \cdot 1 } \cdot \underbrace{ \ldots \cdot 1} \cdot \underbrace{ \ldots \cdot 2} \cdots$$

이 역시 변형된 팩토리얼이며, 다만 크기가 훨씬 작습니다. 이는 $\lfloor n / p \rfloor !_{\%p}$입니다.

따라서 변형된 팩토리얼 $n!_{\%p}$를 계산하는 동안 $O(p)$번의 연산을 수행했고, 이제 $\lfloor n / p \rfloor !_{\%p}$의 계산만 남았습니다. 이로써 재귀적인 공식을 얻습니다. 재귀 깊이는 $O(\log_p n)$이므로, 알고리즘의 전체 점근적 동작은 $O(p \log_p n)$입니다.

팩토리얼 $0!,~ 1!,~ 2!,~ \dots,~ (p-1)!$을 $p$를 법으로 미리 계산해 두면 복잡도는 $O(\log_p n)$이 된다는 점에 유의하십시오.

구현¶

이는 꼬리 재귀에 해당하므로 재귀가 필요하지 않으며, 반복문을 사용하여 쉽게 구현할 수 있습니다. 다음 구현에서는 팩토리얼 $0!,~ 1!,~ \dots,~ (p-1)!$을 미리 계산하므로 실행 시간은 $O(p + \log_p n)$입니다. 함수를 여러 번 호출해야 한다면, 미리 계산하는 부분을 함수 밖에서 수행하고 $n!_{\%p}$의 계산은 $O(\log_p n)$ 시간에 수행할 수 있습니다.

int factmod(int n, int p) {
    vector<int> f(p);
    f[0] = 1;
    for (int i = 1; i < p; i++)
        f[i] = f[i-1] * i % p;

    int res = 1;
    while (n > 1) {
        if ((n/p) % 2)
            res = p - res;
        res = res * f[n%p] % p;
        n /= p;
    }
    return res;
}

또는 메모리가 제한되어 모든 팩토리얼을 저장할 여유가 없다면, 필요한 팩토리얼만 기억해 두고 정렬한 뒤, 팩토리얼 $0!,~ 1!,~ 2!,~ \dots,~ (p-1)!$을 명시적으로 저장하지 않고 루프에서 계산하면서 한 번의 순회로 모두 구할 수도 있습니다.

$p$의 중복도¶

이항 계수를 $p$로 나눈 나머지를 계산하려면 $n!$에서 $p$의 중복도, 즉 $n!$의 소인수분해에서 $p$가 나타나는 횟수, 다시 말해 변형된 팩토리얼을 계산하는 동안 $p$를 제거한 횟수가 추가로 필요합니다.

르장드르 공식을 사용하면 이를 $O(\log_p n)$ 시간에 계산할 수 있습니다. 이 공식은 중복도 $\nu_p$를 다음과 같이 나타냅니다:

$$\nu_p(n!) = \sum_{i=1}^{\infty} \left\lfloor \frac{n}{p^i} \right\rfloor$$

따라서 다음과 같이 구현할 수 있습니다:

int multiplicity_factorial(int n, int p) {
    int count = 0;
    do {
        n /= p;
        count += n;
    } while (n);
    return count;
}

이 공식은 앞 절에서 사용한 것과 같은 아이디어를 이용하여 매우 쉽게 증명할 수 있습니다. 인수 $p$를 포함하지 않는 원소를 모두 제거하십시오. 그러면 $\lfloor n/p \rfloor$개의 원소가 남습니다. 각 원소에서 인수 $p$를 제거하면 곱 $1 \cdot 2 \cdots \lfloor n/p \rfloor = \lfloor n/p \rfloor !$을 얻게 되며, 다시 재귀가 나타납니다.