Hướng dẫn giải

Cho ~N~ và số nguyên tố ~P~. Tìm số mũ lớn nhất của ~P~ chia hết ~N!~.

Sub 1: Đếm từng số — ~O(N)~, dùng khi ~N \le 1000~

Với mỗi ~i~ từ 1 đến ~N~, chia ~i~ cho ~P~ liên tiếp và đếm số lần chia hết. Cộng các số đếm lại.

Nếu chỉ nộp sub này: đúng 21/21 test.

Sub 2: Công thức Legendre — ~O(\log_P N)~, dùng khi mọi trường hợp còn lại

Số mũ của ~P~ trong ~N!~ bằng ~\sum_{k \ge 1} \lfloor N / P^k \rfloor~. Lấy các lũy thừa ~P^k~ cho đến khi vượt quá ~N~. ~P^k~ có thể tới khoảng ~10^{10}~ nên dùng số nguyên 64 bit.

Nếu chỉ nộp sub này: đúng 21/21 test.

Chương trình hoàn chỉnh

Chương trình đọc ~T~ rồi từng cặp ~N, P~. Nếu ~N \le 1000~ thì gọi sub1, ngược lại gọi sub2. Ví dụ: ~N = 62, P = 7~ cho 9; ~N = 76, P = 2~ cho 73; ~N = 3, P = 5~ cho 0.

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

long long N, P;

// Sub 1: vet can. Duyet i = 1..N, moi i dem so lan chia het cho P. O(N), dung khi N <= 1000.
void sub1() {
    long long cnt = 0;
    for (long long i = 1; i <= N; i++)
        for (long long x = i; x % P == 0; x /= P) cnt++;
    cout << cnt << "\n";
}

// Sub 2: cong thuc Legendre. So mu cua P trong N! = sum of floor(N / P^k) voi k >= 1. O(log N).
void sub2() {
    long long cnt = 0;
    for (long long pk = P; pk <= N; pk *= P) cnt += N / pk;
    cout << cnt << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        cin >> N >> P;
        if (N <= 1000) sub1();
        else sub2();
    }
    return 0;
}