Hướng dẫn giải

Cần tìm số mũ của số nguyên tố ~P~ trong phân tích ~N!~ với ~N \le 10^{18}~.

Sub 1: Vét cạn — ~O(N)~, dùng khi ~N \le 10^6~

Với mỗi ~i~ từ 1 đến ~N~, đếm số lần ~P~ chia hết ~i~ (chia liên tiếp) rồi cộng các số đếm lại. Đây là cách đếm trực tiếp theo định nghĩa của ~N!~.

Nếu chỉ nộp sub này: đúng 16/20 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 ~\lfloor N/P \rfloor + \lfloor N/P^2 \rfloor + \lfloor N/P^3 \rfloor + \cdots~. Ta không cần tính ~P^k~ mà chỉ chia liên tiếp: ~t = N/P~, rồi ~t = t/P~ cho đến khi ~t = 0~. Kết quả không vượt quá ~N \le 10^{18}~ nên ~long long~ là đủ.

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

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

Đề có 3 subtask theo ~N~ và ~P~. Sub 1 dùng khi ~N \le 10^6~, sub 2 dùng cho các trường hợp còn lại.

Chương trình đọc ~N, P~. Nếu ~N \le 10^6~ thì gọi sub1, ngược lại gọi sub2.

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

long long N, P;

// Sub 1: vet can, duyet i = 1..N, moi i dem so lan P chia het. Dung khi N <= 10^6
void sub1() {
    long long cnt = 0;
    for (long long i = 1; i <= N; i++) {
        long long t = i;
        while (t % P == 0) { cnt++; t /= P; }
    }
    cout << cnt << "\n";
}

// Sub 2: cong thuc Legendre: so mu cua P trong N! = N/P + N/P^2 + N/P^3 + ...
// Chia lien tiep t = N/P, N/P^2, ... nen chi mat O(log_P N) buoc.
void sub2() {
    long long cnt = 0;
    long long t = N / P;
    while (t > 0) {
        cnt += t;
        t /= P;
    }
    cout << cnt << "\n";
}

int main() {
    freopen("CAU2.INP", "r", stdin);
    freopen("CAU2.OUT", "w", stdout);
    cin >> N >> P;
    if (N <= 1000000) sub1();
    else sub2();
    return 0;
}