สมมติว่าเรามีจำนวนเต็มสองตัว n และ k เราต้องหาค่าสูงสุดของ x เพื่อให้ n! mod (k^x) =0 ดังนั้นเมื่อ n =5 และ k =2 ผลลัพธ์จะเป็น 3 ดังที่ n! =120 ตอนนี้สำหรับค่า x ที่แตกต่างกัน มันจะเป็น −
120 mod 2^0 =0, 120 mod 2^1 =0, 120 mod 2^2 =0, 120 mod 2^3 =0, 120 mod 2^4 =8, 120 mod 2^5 =24, 120 mod 2^6 =56, 120 mod 2^7 =120 เมื่อค่าสูงสุดของ x =3 ผลลัพธ์จะเป็น 0 ดังนั้นผลลัพธ์คือ 3
เพื่อแก้ปัญหานี้ เราต้องทำตามขั้นตอนเหล่านี้ -
- หารากที่สองของ k แล้วเก็บไว้ใน m
- สำหรับ i :=2 ถึง m ให้ทำตามขั้นตอนต่อไปนี้:
- เมื่อ i =m ให้ตั้งค่า i :=k
- ถ้า k หารด้วย i ลงตัว ให้หาร k ด้วย i
- เรียกใช้ลูปไปที่ n และเพิ่มผลหารให้กับตัวแปรที่เรียกว่า u
- เก็บค่าต่ำสุดของ r หลังจากแต่ละลูป
ตัวอย่าง
#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;
int k = 2;
cout<<"Maximum value of x is: " << calculateMaxX(n, k);
} ผลลัพธ์
Maximum value of x is: 3
