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 =엔! / (R! * (N – R)! ). N!, R!을 나누는 P의 가장 큰 거듭제곱에 Legendre Formula를 사용합니다. 그리고 (N – R)! NCR이 P로 나누어 떨어지려면 조건은 N입니다!> 알! + (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