ตรวจสอบว่า nCr หารด้วยจำนวนเฉพาะ P ลงตัวหรือไม่ ใน C++

บทนำ

ให้ตัวแปรสามตัวคือ N, R และ P โดย N และ R ใช้คำนวณ ^NC_R (การจัดหมู่) และ P เป็นจำนวนเฉพาะ เราต้องการทราบว่า ^NC_R หารด้วย P ลงตัวหรือไม่

ตัวอย่าง: N = 7, R = 2, P = 3 → ⁷C₂ = 21 ซึ่งหารด้วย 3 ลงตัว ดังนั้นผลลัพธ์คือ true

หลักการคำนวณ

เรารู้ว่า ^NC_R = N! / (R! × (N - R)!) ใช้ สูตรเลจันดร (Legendre's Formula) เพื่อหกำลังสูงสุดของ P ที่หาร N!, R! และ (N - R)! ลงตัว

เงื่อนไขที่ ^NC_R จะหารด้วย P ลงตัวคือ: กำลังของ P ใน N! ต้องมากกว่าผลรวมของกำลัง P ใน R! และ (N - R)! กล่าวคือ x1 > x2 + x3

ตัวอย่างโค้ด 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) {
    // หากำลังสูงสุดของ p ที่หาร n!, r! และ (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";
    return 0;
}

ผลลัพธ์

nCr is divisible by P