[백준] 11493번: 이항 계수 5

문제

자연수 N과 정수 K가 주어졌을 때 이항 계수 (NK)를 M으로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, K와 M이 주어진다. (1 ≤ N ≤ 4×10^6, 0 ≤ K ≤ N, 2 ≤ M ≤ 4×10^6)

출력

 (NK)를 M으로 나눈 나머지를 출력한다.

 

 

이항 계수의 나머지를 구하는 문제인데, N과 K, M이 모두 크기가 큰 수라 이항 계수를 직접 구해서 계산하는 것으로는 문제를 해결할 수 없습니다. 문제를 해결하기 위해서는, 이항 계수의 성질과 나머지의 성질을 이용해서 문제를 풀어야 합니다. 이항 계수는 N! / (K! * (N - K)!) 라는 것과, 나머지 연산이 곱셈에 대해서는 (A * B) % M = ((A % M) * (A % M)) % M 이라는 것을 알 수 있기 때문에, 이항 계수를 소인수분해해서 안에 있는 소수의 갯수를 세어줍니다. 소수의 갯수만큼 리턴될 변수에 해당 소수를 곱하고, 나머지 연산을 수행해줍니다.

 

#include <iostream>
typedef long long ll;
using namespace std;

bool sieve[4000001];
int numberOfPrime[4000001];

void eratosthenes(int N) {
    for (int i = 2; i * i <= N; i++) {
        if (!sieve[i]) {
            for (int j = i + i; j <= N; j += i) {
                sieve[j] = true;
            }
        }
    }
}

void calculatePrime(int N, int K) {
    for (int i = 2; i <= N; i++) {
        if (!sieve[i]) {
            for (ll factor = i; factor <= N; factor *= i) {
                numberOfPrime[i] += (N / factor) - (K / factor) - ((N - K) / factor);
            }
        }
    }
}

int main() {
    int N, M, K;
    cin >> N >> K >> M;
    eratosthenes(N);
    calculatePrime(N, K);

    ll ans = 1;
    for (int i = 2; i <= N; i++) {
        for (int j = 0; j < numberOfPrime[i]; j++) {
            ans *= i;
            ans %= M;
        }
    }
    cout << ans << '\n';

    return 0;
}