Giả sử có ba biến N, R và P. N và R được sử dụng để lấy N C R và P là một số nguyên tố. Chúng ta phải tìm xem N C R chia hết cho P. Giả sử chúng ta có một số số N =7, R =2 và P =3, thì 7 C 2 =21, giá trị này chia hết cho 3, vì vậy kết quả đầu ra sẽ là true.
Chúng tôi biết rằng N C R =N! / (R! * (N - R)!). Chúng ta sẽ sử dụng Công thức Legendre để tính lũy thừa lớn nhất của P, chia cho bất kỳ N !, R! và (N - R)! để NCR chia hết cho P thì điều kiện là N!> R! + (N - R)!
Ví dụ
#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) {
// Find the highest powers of p
// that divide n!, r! and (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 is divisible by P";
else
cout << "nCr is not divisible by P";
} Đầu ra
nCr is divisible by P