ค้นหาว่า 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)! ). เราจะใช้ Legendre Formula กับพลังที่ใหญ่ที่สุดของ P ซึ่งหาร N!, R! และ (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