หาค่า x สูงสุดที่ทำให้ n! หาร k^x ลงตัวใน C++

โจทย์

ให้จำนวนเต็ม n และ k ต้องการหาค่า x สูงสุดที่ทำให้ n! mod (k^x) = 0

ตัวอย่าง: n=5, k=2 → 5! = 120, 120 mod 2³ = 0, 120 mod 2⁴ = 8 → x = 3

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

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

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

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

int calculateMaxX(int n, int k) {
    int result = n, v, u;
    int m = sqrt(k) + 1;
    for (int i = 2; i <= m && k > 1; i++) {
        if (i == m) i = k;
        for (u = v = 0; k % i == 0; v++) k /= i;
        if (v > 0) {
            int t = n;
            while (t > 0) { t /= i; u += t; }
            result = min(result, u / v);
        }
    }
    return result;
}

int main() {
    int n = 5, k = 2;
    cout << "Maximum value of x is: " << calculateMaxX(n, k);
}

ผลลัพธ์

Maximum value of x is: 3