Giả sử chúng ta có hai số nguyên n và k. Chúng ta phải tìm giá trị lớn nhất của x, sao cho n! mod (k ^ x) =0. Vì vậy, khi n =5 và k =2, thì đầu ra sẽ là 3. As n! =120, bây giờ đối với các giá trị khác nhau của x, nó sẽ là -
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. Vì giá trị lớn nhất của x =3, kết quả là 0, do đó đầu ra là 3.
Để giải quyết vấn đề này, chúng ta phải làm theo các bước sau -
- Lấy căn bậc hai của k và lưu trữ thành m
- Đối với i:=2 to m, hãy thực hiện các bước sau:
- Khi i =m, thì đặt i:=k
- nếu k chia hết cho i thì k chia hết cho i
- Chạy một vòng lặp đến n và thêm thương vào một biến có tên là u.
- Lưu trữ giá trị nhỏ nhất của r, sau mỗi vòng lặp
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);
} Đầu ra
Maximum value of x is: 3