查找nCr是否可被C ++中的给定素数整除

假设存在三个变量N，R和P。N和R用于获得^N C _R，并且P是素数。我们必须找到^N C _R是否可被P整除。假设我们有一些数字N = 7，R = 2和P = 3，那么⁷ C ₂ = 21，这可被3整除，因此输出为真。

我们知道^N C _R = N！/（R！*（N – R）！）。我们将使用Legendre公式获得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