C++でnCrが指定された素数で割り切れるかどうかを判定する方法

3つの変数 N、R、P があるとします。N と R から二項係数 ^NC_R を求め、P は素数とします。このとき、^NC_R が P で割り切れるかどうかを判定するのが本記事の目的です。例えば、N = 7、R = 2、P = 3 の場合、⁷C₂ = 21 となり、21 は 3 で割り切れるため、結果は true となります。

二項係数は一般的に次の式で表されます。

^NC_R = N! / (R! × (N − R)!)

ここでルジャンドルの定理(Legendre's Formula)を活用します。この定理を使うと、N!、R!、(N − R)! のそれぞれを割り切る素数 P の最大のべき乗(指数)を求めることができます。^NC_R が P で割り切れる条件は、N! に含まれる P の指数が、R! と (N − R)! に含まれる P の指数の合計よりも大きくなること、すなわち x(N!) > x(R!) + x((N − R)!) が成り立つことです。

アルゴリズムの仕組み

関数 getPower(n, p) は、ルジャンドルの定理に基づいて n! を割り切る素数 p の指数を計算します。具体的には、n を p で繰り返し割りながらその商を加算していくことで、⌊n/p⌋ + ⌊n/p²⌋ + ⌊n/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) {
   // n!、r!、(n - r)! それぞれを割り切る
   // p の最大のべき乗を求める
   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

この例では N = 7、R = 2、P = 7 としています。⁷C₂ = 21 は 7 で割り切れるため、プログラムは「nCr is divisible by P」と出力します。この方法を使えば、階乗の値を直接計算することなく大きな N に対してもオーバーフローを避けながら効率的に判定できます。