[C++][백준] 13977 이항계수와 쿼리

이 문제는 빠른 팩토리얼 연산을 하면 해결할 수 있다.
우리가 사용할 연산 방법은 페르마의 소정리를 이용해서 문제를 해결하는 방법이다.

<페르마의 소정리가 무엇일까?>
임의의 소수 p와 p!=a 인 임의의 자연수 a에 대해 a^p-1 == 1(mod p) 가 성립한다. 라는 정리이다.

이 정리를 이용하면 a^-1 == a^p-2(mod p) 라는 것을 유도할 수 있다.

이제 코드를 보자

#include<bits/stdc++.h>
#define N 4000000
#define MOD 1000000007
using namespace std;
using ll = long long;
ll M;
ll c,R;
ll fac[N + 1], facinv[N + 1];

ll power(ll base, ll index) {
    ll r = 1;
    while (index) {
        if (index & 1) r = (r * base) % MOD;
        base = (base * base) % MOD;
        index >>= 1;
    }
    return r;
}

ll comb(ll n, ll k) {
    ll r = (fac[n] * facinv[n - k]) % MOD;
    r = (r * facinv[k]) % MOD;
    return r;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    fac[0] = fac[1] = facinv[0] = facinv[1] = 1;
    for (int i = 2; i <= N; ++i) {
        fac[i] = (fac[i - 1] * i) % MOD;
        facinv[i] = power(fac[i], MOD - 2);
    }
    cin >> M;
    for(int j=0; j<M; j++)
    {
        cin >> c >> R;
        cout << comb(c,R) << '\n';
    }


}