C++-এ nCr যেন প্রদত্ত প্রাইম দ্বারা বিভাজ্য কিনা তা যাচাই করা

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

আমরা জানি ^NC_R = N! / (R! * (N - R)! )। আমরা লেজান্ড্রের সূত্র ব্যবহার করব যেকোনো N!, R! এবং (N - R)! কে বিভাজ্য করা P-এর সর্বোচ্চ ঘাত বের করতে, যাতে NCR P দ্বারা বিভাজ্য হয়, শর্ত হল N! > R! + (N - R)!।

C++ প্রোগ্রাম উদাহরণ

#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";
    return 0;
}

আউটপুট

nCr is divisible by P