nCrがC++で指定された素数で割り切れるかどうかを調べます

3つの変数N、R、およびPがあるとします。NとRは、 ^N を取得するために使用されます。 C _R Pは素数です。 ^N かどうかを確認する必要があります C _R はPで割り切れる。いくつかの数N=7、R =2、P =3があるとすると、 ⁷ C ₂ =21、これは3で割り切れるので、出力はtrueになります。

^N C _R =N！ /（R！*（N – R）！）。ルジャンドルの公式を使用して、任意のN！、R！を分割するPの最大の累乗にします。および（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