C++에서 nCr이 주어진 소수로 나누어 떨어지는지 확인하는 방법

세 개의 변수 N, R, P가 있다고 가정해 보겠습니다. N과 R은 이항계수 ^NC_R을 구하는 데 사용되며, P는 소수입니다. 우리의 목표는 ^NC_R이 P로 나누어 떨어지는지 판별하는 것입니다. 예를 들어 N = 7, R = 2, P = 3이라면 ⁷C₂ = 21이고, 21은 3으로 나누어 떨어지므로 결과는 참(true)이 됩니다.

^NC_R은 다음과 같이 정의됩니다.

^NC_R = N! / (R! × (N − R)!)

접근 방법: 르장드르 공식(Legendre's Formula)

이 문제를 효율적으로 해결하려면 르장드르 공식을 활용할 수 있습니다. 르장드르 공식은 임의의 계승(factorial) 값을 나누는 소수 P의 최대 거듭제곱(지수)을 구하는 공식입니다. N!, R!, (N − R)! 각각에 대해 P의 지수를 구한 뒤, 다음 조건을 만족하는지 확인하면 됩니다.

N!의 P 지수 > R!의 P 지수 + (N − R)!의 P 지수

이 조건이 성립하면 분자에 포함된 P 인수의 개수가 분모보다 많다는 의미이므로, 약분 후에도 P가 남아 있게 되어 ^NC_R은 P로 나누어 떨어집니다.

예를 들어 10!에 포함된 3의 지수를 구하면 ⌊10/3⌋ + ⌊10/9⌋ = 3 + 1 = 4가 됩니다. 이처럼 n을 p로 반복해서 나누면서 몫을 모두 더하면 원하는 지수를 빠르게 얻을 수 있습니다.

알고리즘

1. getPower(n, p): n을 p로 계속 나누면서 몫을 누적하여 n!을 나누는 p의 최대 지수를 반환합니다.
2. isDivisibleByP(n, r, p): N!, R!, (N − R)!에 대한 지수를 각각 구하고, x1 > x2 + x3 조건을 검사합니다.
3. 조건이 참이면 true, 그렇지 않으면 false를 반환합니다.

예제 코드

#include <iostream>
using namespace std;

// n!을 나누는 p의 최대 지수를 구하는 함수
int getPower(int n, int p) {
    int pow = 0;
    while (n) {
        n /= p;
        pow += n;
    }
    return pow;
}

bool isDivisibleByP(int n, int r, int p) {
    // n!, r!, (n - r)!을 나누는 p의 최대 거듭제곱 구하기
    int x1 = getPower(n, p);
    int x2 = getPower(r, p);
    int x3 = getPower(n - r, p);
    if (x1 > x2 + x3)
        return true;
    return false;
}

int main() {
    int n = 7, r = 2, p = 7;
    if (isDivisibleByP(n, r, p))
        cout << "nCr is divisible by P";
    else
        cout << "nCr is not divisible by P";
}

출력 결과

nCr is divisible by P

위 예제에서 ⁷C₂ = 21이고, 21은 7로 나누어 떨어지므로 "nCr is divisible by P"가 출력됩니다. 이 방법은 실제로 ^NC_R의 큰 값을 직접 계산하지 않고도 판별할 수 있기 때문에, N이 매우 큰 경우에도 오버플로우 없이 효율적으로 동작한다는 장점이 있습니다.