정수 $a$를 $m$으로 나눈 나머지 연산의 곱셈 역원은 $a \times a^{-1} \equiv 1 \pmod m$을 만족하는 $a^{-1}$을 말합니다.

즉, $a^{-1} \equiv x \pmod m$을 만족하는 $x$를 말합니다.

역원은 $a$와 $m$이 서로소인 경우에만 존재합니다.

역원을 구하는 코드를 작성해보면 아래와 같습니다.

for (int i=1; i<m; i++) {
    if ((a*i) % m == 1) {
        x = i;
    }
}

위 소스의 시간 복잡도는 O($m$) 입니다. 조금 더 빠른 시간에 구할 수 있는 방법은 뭐가 있을까요?

첫 번째 방법은 확장 유클리드 알고리즘을 이용하는 방법입니다.

$ax = 1 \pmod m$ 을 구해야 하기 때문에, $ax = 1 + my$로 바꿔서 쓸 수 있습니다.

다시 $ax - my = 1$로 바꿔쓸 수 있고, $x$와 $y$는 음수가 되어도 상관없기 때문에, $ax + my = 1$로 바꿔 쓸 쑤 있습니다.

이제 확장 유클리드 알고리즘을 이용해 $x$의 값을 구하면 됩니다.

$m$이 소수인 경우에는 페르마의 소정리를 이용해서 구할 수 있습니다.

$m$이 소수이고, $a$와 $m$이 서로소라면, $a^{m-1}$은 $m$으로 나눈 나머지는 1입니다.

즉, 이 말은 $a^{m-1} \equiv 1 \pmod m$ 이라는 의미가 됩니다.

따라서, $a^{m-1} = a \times a^{m-2} \equiv 1 \pmod m$이 되고

$a^{m-2}$가 $a \times x \equiv 1 \pmod m$을 만족하는 $x$가 되기 때문에, 역원은 $a^{m-2}$가 됩니다.

11401번 문제: 이항 계수 3은 자연수 $N$과 정수 $K$가 주어졌을 때 이항 계수 $\binom{N}{K}$를 1,000,000,007로 나눈 나머지를 구하는 문제입니다.

즉, $N! / (K!(N-K)!$를 $M$ = 1,000,000,007로 나눈 나머지를 구하는 문제입니다.

$A = N!$, $B = K!(N-K)!$ 이라고 한다면, $A/B \pmod M$을 구해야 합니다.

$M$이 소수이기 때문에, 페르마의 소정리를 이용할 수 있습니다. 따라서 ,구해야 하는 값은 $A \times B^{M-2} \pmod M$이 됩니다.

어떤 수의 제곱은 로그 시간 만에 구할 수 있기 때문에, 다음과 같이 코드를 작성할 수 있습니다.

#include <iostream>
using namespace std;
long long mul(long long x, long long y, long long p) {
    long long ans = 1;
    while (y > 0) {
        if (y%2 != 0) {
            ans *= x;
            ans %= p;
        }
        x *= x;
        x %= p;
        y/=2;
    }
    return ans;
}
int main() {
    long long n,r,p;
    cin >> n >> r;
    p = 1000000007LL;
    long long ans = 1;
    long long t1 = 1;
    long long t2 = 1;
    for (long long i=1; i<=n; i++) {
        t1 *= i;
        t1 %= p;
    }
    for (long long i=1; i<=r; i++) {
        t2 *= i;
        t2 %= p;
    }
    for (long long i=1; i<=n-r; i++) {
        t2 *= i;
        t2 %= p;
    }
    long long t3 = mul(t2,p-2,p);
    t3 %= p;
    ans = t1*t3;
    ans %= p;
    cout << ans << '\n';
    return 0;
}