数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学在 C++ 中判断 nCr 是否能被给定的素数整除
假设有三个变量 N、R 和 P。N 和 R 用于计算 NCR，P 是一个素数。我们需要判断 NCR 是否能被 P 整除。例如，如果 N = 7，R = 2，P = 3，则 7C2 = 21，它能被 3 整除，所以输出为 true。
我们知道 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) {
// 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";
}输出
nCr is divisible by P
更新于：2019年10月21日
浏览量：114
广告