Cho hai số nguyên n và k. Ta cần tìm giá trị lớn nhất của x sao cho n! chia hết cho k^x (tức n! % (k^x) = 0). Ví dụ: n = 5, k = 2, kết quả là 3. Vì 5! = 120, và 120 chia hết cho 2^0, 2^1, 2^2, 2^3 nhưng không chia hết cho 2^4.
Để giải bài toán này, ta thực hiện các bước sau:
- Tính căn bậc hai của k, lưu vào m.
- Duyệt i từ 2 đến m:
- Nếu i == m thì gán i = k.
- Nếu k chia hết cho i, chia k cho i và đếm số lần chia (v).
- Tính tổng các thương khi chia n liên tiếp cho i (biến u) - đây là công thức Legendre để tìm số mũ của thừa số nguyên tố i trong n!.
- Cập nhật kết quả = min(kết quả, u / v).
Ví dụ
#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);
}
Kết quả
Maximum value of x is: 3