Tìm K
Đề bài
Cho hai số nguyên dương $N$ và $M$ $(2 \le N, M \le 10^9)$. Hãy tìm số nguyên dương $K$ lớn nhất sao cho $N!$ chia hết cho $M^K$.
Dữ liệu vào: gồm một dòng duy nhất chứa 2 số nguyên dương $N, M$.
Kết quả: ghi số nguyên $K$ tìm được. Các test được cho luôn đảm bảo tìm được giá trị $K$ hợp lệ.
Giới hạn: thời gian 1 giây, bộ nhớ 256 MB.
Subtask:
- 20% điểm đầu tiên có $N, M \le 20$.
- 30% điểm tiếp theo có $N, M \le 10^5$.
- 30% điểm tiếp theo có $N, M \le 10^7$.
- 20% điểm còn lại không có giới hạn gì thêm.
6 62Giải thích ví dụ: $6! = 720 = 2^4 \cdot 3^2 \cdot 5$. Ta có $6^2 = 36$ và $720 = 36 \cdot 20$ nên chia hết; còn $6^3 = 216$ thì $720 / 216$ không nguyên. Vậy $K = 2$.
Lời mở đầu
$N!$ với $N = 10^9$ là một con số khổng lồ (hàng tỉ chữ số), không cách nào tính ra được. Bí quyết của bài là không bao giờ tính $N!$, mà chỉ làm việc với số mũ của các thừa số nguyên tố. Mình sẽ đi từ cách "tính thẳng" ăn subtask 1, đến cách đếm số mũ trong từng số, rồi tới công thức Legendre chạy chỉ vài chục phép tính.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test chính thức có gì?
Bộ test có 100 test, chia thành 4 nhóm đúng như 4 subtask:
| Test | N | M | Đáp án K | M nguyên tố | Số thừa số nguyên tố khác nhau của M (tối đa) |
|---|---|---|---|---|---|
| 1–20 | 4 – 19 | 2 – 19 | 1 – 5 | 5 test | 2 |
| 21–50 | 13.441 – 100.000 | 10 – 97.016 | 25 – 16.662 | 2 test | 4 |
| 51–80 | 1.000.828 – 10.000.000 | 24 – 8.098.458 | 31 – 3.333.330 | 2 test | 5 |
| 81–100 | 100.700.944 – 1.000.000.000 | 54 – 996.509.461 | 277 – 105.983.880 | 1 test | 5 |
- Mỗi test chỉ có đúng 2 số $N, M$. Đáp án nhỏ nhất là 1, đúng như đề hứa "luôn tìm được $K$ hợp lệ" (tức là $M$ không có thừa số nguyên tố nào lớn hơn $N$).
- Có cả $M$ là số nguyên tố (ví dụ test cuối cùng của subtask 4 có $M$ gần $10^9$), $M$ là lũy thừa của 2, và $M$ có tới 5 thừa số nguyên tố khác nhau.
- Các nhóm test khớp đúng với subtask của đề:
| Subtask | Điều kiện | Các test | Cách ăn được |
|---|---|---|---|
| 1 (20%) | $N, M \le 20$ | 1 – 20 | Cách 1, 2, 3 |
| 2 (30%) | $N, M \le 10^5$ | 21 – 50 | Cách 2, 3 |
| 3 (30%) | $N, M \le 10^7$ | 51 – 80 | Cách 2, 3 |
| 4 (20%) | $N, M \le 10^9$ | 81 – 100 | Cách 3 |
Ý tưởngSo số mũ của từng thừa số nguyên tố
Phân tích $M$ ra thừa số nguyên tố: $M = p_1^{e_1} \cdot p_2^{e_2} \cdots p_s^{e_s}$. Khi đó $M^K = p_1^{K e_1} \cdots p_s^{K e_s}$.
Gọi $v_p(N!)$ là số mũ của $p$ trong $N!$. Một số chia hết cho $M^K$ khi và chỉ khi với mọi thừa số $p_i$, số mũ của $p_i$ trong nó đủ lớn:
Như ví dụ: $M = 6 = 2^1 \cdot 3^1$, $6! = 2^4 \cdot 3^2 \cdot 5$ → $K = \min(4/1,\ 2/1) = 2$. Thừa số 3 là "nút cổ chai".
Còn $v_p(N!)$ thì tính bằng công thức Legendre: trong các số $1, 2, \ldots, N$ có $\lfloor N/p \rfloor$ số chia hết cho $p$ (mỗi số góp ít nhất 1 thừa số $p$), có $\lfloor N/p^2 \rfloor$ số chia hết cho $p^2$ (góp thêm 1 thừa số nữa), ... Cộng lại:
Ví dụ $v_2(10!) = 5 + 2 + 1 = 8$: có 5 số chẵn (2, 4, 6, 8, 10), trong đó 2 số chia hết cho 4 (4, 8) và 1 số chia hết cho 8 (8). Đúng là $10! = 2^8 \cdot 3^4 \cdot 5^2 \cdot 7$.
Em nhập $N, M$ rồi bấm Tiếp để xem từng bước: phân tích $M$ vào một cái map, rồi tính Legendre cho từng thừa số:
Cách 1Tính thẳng N! rồi chia – chỉ cho N ≤ 20
Với $N \le 20$ thì $N! \le 20! \approx 2{,}43 \cdot 10^{18}$, vẫn vừa kiểu unsigned long long (tối đa khoảng $1{,}8 \cdot 10^{19}$). Ta tính $N!$, rồi cứ chia cho $M$ khi còn chia hết, đếm số lần chia.
- Chia $f$ cho $M$ được $K$ lần (mà vẫn nguyên) nghĩa là $M^K \mid N!$, nên đếm số lần chia chính là $K$ lớn nhất.
- Khi $N \ge 21$ thì $f$ bị tràn số. Tệ hơn nữa: từ $N \ge 66$, $N!$ có hơn 64 thừa số 2 nên $f$ (tính theo modulo $2^{64}$) bằng đúng 0, và vòng
while(f % m == 0)chạy mãi không dừng! - Bản Python có số nguyên lớn nên không tràn, nhưng nhân ra $N!$ với $N = 10^5$ đã là một số hơn 450 nghìn chữ số, chậm khủng khiếp.
Kết quả chạy thật: bản C++ đúng 20/100 test (Subtask 1: 20/20, Subtask 2: 0/30, Subtask 3: 0/30, Subtask 4: 0/20). Subtask 1 đúng hết; mọi test từ 21 trở đi đều quá thời gian vì vòng while chạy vô tận khi $f$ tràn số về 0.
Cách 2Phân tích M bằng map + đếm số mũ trong từng số – O(N)
Bây giờ ta làm theo ý tưởng: phân tích $M$ ra thừa số nguyên tố, lưu vào map<long long, int> mp với mp[p] = số mũ của $p$ trong $M$. Phân tích bằng cách thử chia $p = 2, 3, 4, \ldots$ khi $p^2 \le x$; phần còn lại $x > 1$ cuối cùng chắc chắn là một số nguyên tố.
Còn $v_p(N!)$ thì tính "thủ công": $v_p(N!)$ $= v_p(1) + v_p(2) + \cdots + v_p(N)$, với mỗi số $i$ ta chia cho $p$ đến khi không chia được nữa.
- Vòng phân tích chỉ chạy tới $\sqrt{M} \le 31623$ nên rất nhanh. Khi chia hết thì $x$ giảm ngay, nên điều kiện
p * p <= xcàng dừng sớm. - Duyệt
mapbằngfor(auto [p, e] : mp)(cú pháp C++17) lấy ra lần lượt từng cặp (thừa số, số mũ). - Mỗi thừa số tốn $O(N)$ bước, $M \le 10^9$ có tối đa 9 thừa số nguyên tố khác nhau. Với $N = 10^9$ thì quá chậm.
Kết quả chạy thật: bản C++ đúng 81/100 test (Subtask 1: 20/20, Subtask 2: 30/30, Subtask 3: 30/30, Subtask 4: 1/20). Subtask 3 ($N \le 10^7$) chạy tối đa 0.30 giây; subtask 4 với $N$ cỡ $10^8$–$10^9$ thì chỉ qua được 1/20 test (test có $N$ nhỏ nhất cỡ $10^8$ và $M$ chỉ có 1 thừa số), còn lại quá thời gian.
Cách 3Công thức Legendre – O(√M + log N)
Thay vòng $O(N)$ bằng công thức Legendre. Thay vì tính $p^2, p^3, \ldots$ (dễ tràn số), mình chia dần: q = N, rồi lặp q /= p; cnt += q;. Sau lần chia thứ $i$ thì $q = \lfloor N / p^i \rfloor$ (vì $\lfloor \lfloor N/p^{i-1} \rfloor / p \rfloor$ $= \lfloor N/p^i \rfloor$).
- Vòng
while(q > 0)chạy $\log_p N \le 30$ lần cho mỗi thừa số. kkhởi tạo bằngLLONG_MAXđể lầnminđầu tiên luôn lấy giá trị thật. Vì $M \ge 2$ nênmpluôn có ít nhất 1 thừa số.- Dùng
long longchopđểp * pkhông bị tràn khi $p$ gần $\sqrt{10^9}$.
Kết quả chạy thật: bản C++ đúng 100/100 test (Subtask 1: 20/20, Subtask 2: 30/30, Subtask 3: 30/30, Subtask 4: 20/20). Test lâu nhất chỉ 0.004 giây.
Tổng kếtKết quả chạy thật trên bộ test
Mình chấm cả 3 cách (C++ và Python) trên toàn bộ 100 test với giới hạn 1 giây, đo thời gian CPU (máy chấm của mình lúc chạy đang khá tải):
| Lời giải | Subtask 1 test 1–20 | Subtask 2 test 21–50 | Subtask 3 test 51–80 | Subtask 4 test 81–100 | Tổng | CPU lớn nhất (test đúng) |
|---|---|---|---|---|---|---|
| Cách 1 – C++ | 20/20 | 0/30 | 0/30 | 0/20 | 20/100 | 0.00s |
| Cách 1 – Python | 20/20 | 8/30 | 0/30 | 0/20 | 28/100 | 0.65s |
| Cách 2 – C++ | 20/20 | 30/30 | 30/30 | 1/20 | 81/100 | 0.91s |
| Cách 2 – Python | 20/20 | 30/30 | 2/30 | 0/20 | 52/100 | 0.67s |
| Cách 3 – C++ | 20/20 | 30/30 | 30/30 | 20/20 | 100/100 | 0.00s |
| Cách 3 – Python | 20/20 | 30/30 | 30/30 | 20/20 | 100/100 | 0.03s |
Nhận xét
Đăng nhận xét