Kiểm tra nCr có chia hết cho số nguyên tố P trong C++

Cho ba biến N, R và P. N và R dùng để tính tổ hợp ^NC_R, P là một số nguyên tố. Ta cần xác định xem ^NC_R có chia hết cho P hay không. Ví dụ: N = 7, R = 2, P = 3, thì ⁷C₂ = 21, chia hết cho 3, kết quả là true.

Ta biết ^NC_R = N! / (R! * (N - R)!). Sử dụng công thức Legendre để tìm lũy thừa lớn nhất của P chia hết N!, R! và (N - R)!. Điều kiện để NCR chia hết cho P là lũy thừa của P trong N! lớn hơn tổng lũy thừa trong R! và (N - R)!.

Ví dụ minh họa

#include <iostream>
using namespace std;

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) {
    // Tìm lũy thừa cao nhất của p chia hết n!, r! và (n - r)!
    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 chia het cho P";
    else
        cout << "nCr khong chia het cho P";
    return 0;
}

Kết quả

nCr chia het cho P