หาเลขชี้กำลังสูงสุดของจำนวนที่หาร Factorial ลงตัวใน C++

โจทย์

ให้จำนวน n และ fact ต้องการหาเลขชี้กำลังสูงสุดของ n ที่หาร fact! ลงตัว

ตัวอย่าง: fact=5, n=2 → 5! = 120, 2³=8 หาร 120 ลงตัว, 2⁴=16 ไม่ลงตัว → คำตอบ 3

วิธีแก้ปัญหา (Legendre's Formula)

1. แยกเฉพาะตัวประกอบของ n
2. สำหรับแต่ละเฉพาะตัว p หาเลขชี้กำลังใน fact! ด้วยสูตร: fact/p + fact/p² + fact/p³ + ...
3. หารด้วยเลขชี้กำลังของ p ใน n
4. คำตอบ = min ของทุกเฉพาะตัว

ตัวอย่างโค้ด C++

#include <iostream>
#include <cmath>
using namespace std;

int getPowerPrime(int fact, int p) {
    int res = 0;
    while (fact > 0) { res += fact / p; fact /= p; }
    return res;
}

int findMinPower(int fact, int n) {
    int res = INT_MAX;
    for (int i = 2; i <= sqrt(n); i++) {
        int cnt = 0;
        if (n % i == 0) { cnt++; n = n / i; }
        if (cnt > 0) {
            int curr = getPowerPrime(fact, i) / cnt;
            res = min(res, curr);
        }
    }
    if (n >= 2) {
        int curr = getPowerPrime(fact, n);
        res = min(res, curr);
    }
    return res;
}

int main() {
    int fact = 146, n = 5;
    cout << "Minimum power: " << findMinPower(fact, n);
}

ผลลัพธ์

Minimum power: 35