在 C++ 中判断 nCr 是否能被给定的素数整除
c++server side programmingprogramming更新于 2025/3/15 9:07:17
假设有三个变量 N、R 和 P。N 和 R 用于得到 NCR，而 P 是素数。我们必须判断 NCR 是否能被 P 整除。假设我们有一些数字 N = 7、R = 2 和 P = 3，那么 7C2 = 21，这能被 3 整除，因此输出为真。
我们知道 NCR = N! / (R! * (N – R)! )。我们将使用勒让德公式来计算 P 的最大幂，它可以整除任何 N!、R! 和 (N – R)!为了使 NCR 能被 P 整除，条件是 N! > R! + (N - R)!
示例
#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) {
// 找到 p 的最高幂
// 能整除 n!、r! 和 (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 能被 P 整除";
else
cout << "nCr 不能被 P 整除";
}
输出
nCr 能被 P 整除
