Lời giải: Wilson mở rộng

Phân tích

Wilson mở rộng: Với \(p\) lẻ, \((p^k - 1)! \equiv -1 \pmod{p^k}\) nếu \(p^k = 4\) hoặc \(p^k\) lẻ. Với \(p = 2\) và \(k \ge 3\), \((2^k - 1)! \equiv 1 \pmod{2^k}\). Tuy nhiên nếu \(p^k\) quá lớn, kết quả có thể là 0 do giai thừa chứa \(p\) làm nhân tử.

Độ phức tạp: \(O(p^k)\).

Code mẫu C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    int p, k;
    cin >> p >> k;
    long long mod = 1;
    for (int i = 0; i < k; i++) mod *= p;
    long long fact = 1;
    for (long long i = 2; i <= mod - 1; i++)
        fact = fact * i % mod;
    cout << fact << endl;
    return 0;
}