資料結構
網路
關係資料庫管理系統 (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
廣告