C++ এ প্রদত্ত প্রাইম দ্বারা nCr বিভাজ্য কিনা তা খুঁজুন

ধরুন N, R এবং P তিনটি ভেরিয়েবল আছে। ^N পেতে N এবং R ব্যবহার করা হয়। C_R এবং P একটি প্রধান। আমাদের খুঁজে বের করতে হবে ^N কিনা C_R P দ্বারা বিভাজ্য। ধরুন আমাদের কিছু সংখ্যা N =7, R =2 এবং P =3 আছে, তারপর ⁷ C₂ =21, এটি 3 দ্বারা বিভাজ্য, তাই আউটপুট সত্য হবে।

আমরা জানি যে ^N C_R =N! / (R! * (N – R)!)। আমরা P এর বৃহত্তম শক্তিতে Legendre সূত্র ব্যবহার করব, যা যেকোনো 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