[Fermat's little theorem] 페르마의 소정리

 페르마의 소정리는 아래와 같이 정의 된다. 

 (전제 조건) a와 m이 서로소여야 하며, m이 소수일 경우

$$ a^{m-1} \equiv 1 \ (mod \ m)$$

페르마의 소정리가 왜 필요할까? 보통은 modulus 연산의 나눗셈을 구하기 위한 응용으로 많이 사용된다. 

다시 말하자면, 위의 수식을 아래와 같이 정리해 볼 수 있다는 말이다. 

$$ a^{m-2} \equiv a^{-1} \ (mod \ m)$$

 

modular 연산은 덧셈, 뺄셈, 곱셈에 대해서는 분배 법칙이 성립한다. 

$$ (a+b) \ mod \ m = a \ mod \ m + b \ mod \ m $$

$$ (a-b) \ mod \ m = a \ mod \ m - b \ mod \ m $$

$$ (a \times b) \ mod \ m = a \ mod \ m \times b \ mod \ m $$

 

나눗셈에 대해서는 성립하지 않게 때문에 다음과 같이 전개 해야 한다. 

(전제 조건인 b와 m은 서로소이며, m은 소수를 만족한다고 가정한다.)

$$ (a \div b) \ mod \ m = a \ mod \ m * b^{-1} \ mod \ m = a \ mod \ m * b^{m-2} \ mod \ m$$

 

이를 적용하기 위해 다음의 문제를 보자.

 페르마의 소정리가 필요하다는 것을 알겠는가? 나머지를 출력한다는 점에서 modular 연산을 알 수 있고 이항 계수를 수식으로 전개하면 다음과 같다는 것을 알 수 있다. 

 

$$ {N \choose K} = \frac{N!}{K! * (N-K)!} $$

 

분자와 분모를 모두 구해주고(최대 400만 밖에 되지 않는다), 분모에 페르마의 소정리를 이용해서 modular 연산을 해주는 것이다. 한가지 유의해야 하는 점의 modular연산의 수가 상당히 커서 for문으로 접근하면 시간 초과가 난다는 사실이다. 분할정복의 개념을 이용해서 구하는 방법은 아래 코드의 mpow부분을 유의해서 보면 된다. 

 

const int MOD = 1'000'000'007;

int mpow(int x, int y, int m) {
    if (y == 0) return 1;
    if (y == 1) return x;
    ll ans = mpow(x, y/2, m);
    ans = (ans*ans) % m;
    if (y&1) ans = (ans*x)%m;
    return ans;
}

void solve() {
    int n, k;
    cin >> n >> k;

    ll nomi = 1, denomi1 = 1, denomi2 = 1;
    for(int i=2;i<=n;++i) nomi = (nomi*i)%MOD;
    for(int i=2;i<=k;++i) denomi1 = (denomi1*i)%MOD;
    for(int i=1;i<=n-k;++i) denomi2 = (denomi2*i)%MOD;
    int ans = nomi * mpow((denomi1*denomi2)%MOD, MOD-2, MOD)%MOD;
    cout << ans << '\n';
}


int main() {
    fastio;
    solve();
    return 0;
}