Algorithm - Fermat's little theorem(페르마의 소정리)

개념

If p is prime and a is an integer not divisible by p, then

Fermat's little theorem

Fermat's little theorem

---

문제

16134 조합

www.acmicpc.net/problem/16134

16134번: 조합 (Combination)

---

코드

#include <bits/stdc++.h>
using namespace std;

constexpr long long MOD = 1000000007;

long long pow(long long x, long long y) {
    long long result = 1L;
    while (y) {
        if (y & 1) {
            result *= x;
            result %= MOD;
        }

        x *= x;
        x %= MOD;
        y /= 2L;
    }

    return result;
}

long long permutation(long long n) {
    long long result = 1L;
    for (long long i = 1L;i <= n;++i) {
        result *= i;
        result %= MOD;
    }

    return result;
}

long long combination(long long n, long long r) {
    return permutation(n) * pow(permutation(n - r), MOD - 2) % MOD * pow(permutation(r), MOD - 2) % MOD;
}

int main() {
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

    long long n, r;
    cin >> n >> r;

    cout << combination(n, r) << "\n";
}