Tận cùng khác 0

Nguồn: CLUE OJ – Chương 47: Các bài tập về số nguyên tố Độ khó: Khá BCNN Lũy thừa nguyên tố Tính trước

Đề bài

Cho một số nguyên dương $N$.

Yêu cầu: tìm chữ số tận cùng khác $0$ của giá trị $[1, 2, \ldots, N]$.

Trong đó: kí hiệu $[a_1, a_2, \ldots, a_M]$ là bội chung nhỏ nhất của $a_1, a_2, \ldots, a_M$.

Dữ liệu: gồm một số dòng, mỗi dòng gồm một số nguyên dương $N$ $(N \le 10^6)$. Input có tối đa $10^6$ dòng.

Kết quả: ghi ra kết quả tương ứng với mỗi số $N$ cần tìm.

Các giới hạn: $40\%$ số điểm có $N \le 50$; $60\%$ số điểm còn lại không giới hạn gì thêm. Thời gian 1 giây, bộ nhớ 256 MB.

Ví dụ – input

6
5
4

Ví dụ – output

6
6
2

Giải thích ví dụ: với $N = 6$ thì $[1, 2, 3, 4, 5, 6] = 60$ nên chữ số tận cùng khác $0$ là $6$; với $N = 5$: $[1..5] = 60$ → $6$; với $N = 4$: $[1, 2, 3, 4] = 12$ → $2$.

Lời mở đầu

$\text{BCNN}(1, \ldots, 10^6)$ là con số có hơn $430\,000$ chữ số, lại phải trả lời tới $10^6$ câu hỏi. Ta cần hiểu BCNN này được tạo thành từ những lũy thừa nguyên tố nào, rồi chỉ theo dõi chữ số cuối. Mình đi từ cách tính thẳng BCNN (ăn $40\%$), sang cách tính theo công thức cho từng câu hỏi, rồi tới cách tính trước đáp án cho mọi $N$.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test100 test, 2 mứcÝ tưởngBCNN = tích p^kCách 1tính thẳng BCNNCách 2công thức mỗi câu hỏiCách 3tính trước mọi NTổng kếtkết quả chạy thật

Bộ testBộ test chính thức có gì?

Test	Số dòng (số câu hỏi)	N
1–40	3 – 20	1 … 50
41–100	11.202 – 1.000.000	1 … 1.000.000

• Nhóm 1 khớp $40\%$ đầu ($N \le 50$), mỗi test rất ít câu hỏi.
• Nhóm 2 có tới $10^6$ câu hỏi trong một test (test 100 hỏi đủ $N = 1, 2, \ldots, 10^6$): mỗi câu hỏi phải trả lời gần như $O(1)$, và phải đọc/ghi thật nhanh.

Ý tưởngBCNN(1..N) là tích các lũy thừa nguyên tố lớn nhất

Với mỗi số nguyên tố $p \le N$, số mũ của $p$ trong $\text{BCNN}(1..N)$ bằng số mũ lớn nhất của $p$ trong các số $1..N$, tức là $k$ lớn nhất với $p^k \le N$:

Công thức

$$\text{BCNN}(1, \ldots, N) = \prod_{p \le N,\ p \text{ nguyên tố}} p^{\,k_p}, \qquad k_p = \max\{k : p^k \le N\}$$

Các chữ số $0$ ở cuối sinh ra từ các cặp $(2, 5)$. Gọi $e_2 = k_2$, $e_5 = k_5$ (luôn có $e_2 \ge e_5$ vì $2^{k} \le 5^{k}$). Bỏ đi $e_5$ cặp $(2, 5)$, phần còn lại không chia hết cho $10$:

Chữ số khác 0 cuối cùng

$$\text{đáp án} = \Big( 2^{\,e_2 - e_5} \cdot \prod_{p \ne 2, 5} p^{\,k_p} \Big) \bmod 10$$

Quan sát thêm: khi tăng $N$ lên $N + 1$, BCNN chỉ thay đổi khi $N + 1 = p^k$ là một lũy thừa của số nguyên tố – lúc đó BCNN được nhân thêm đúng một thừa số $p$. Em nhập $N$ rồi bấm Tiếp để xem BCNN "lớn dần":

N =

Ví dụ nhanh:

Cách 1Tính thẳng BCNN bằng số nguyên lớn – chỉ cho N ≤ 50

Dùng $\text{BCNN}(L, i) = L / \gcd(L, i) \cdot i$ cộng dồn từ $i = 2$ tới $N$, rồi xoá các chữ số $0$ ở cuối. Với $N \le 50$, $\text{BCNN}(1..50) \approx 3{,}1 \cdot 10^{21}$ vượt unsigned long long nhưng vừa kiểu __int128 của C++ (tới $\approx 1{,}7 \cdot 10^{38}$).

C++▶ Chạy tay từng dòng codeCách 1: cộng dồn L = BCNN(L, i) bằng Euclid, rồi xoá các chữ số 0 ở cuối.

Dữ liệu vào (stdin) – sửa thoải mái6 5 4

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Mỗi câu hỏi tốn $O(N)$ phép gcd trên số lớn. Với $N$ lớn hơn khoảng $88$, BCNN vượt cả __int128 và bị tràn số.
• Bản Python có số nguyên lớn nên luôn tính đúng, nhưng BCNN của $10^6$ số có hàng trăm nghìn chữ số – quá chậm.

Không gian$O(1)$

Thời gian$O(N)$ phép tính số lớn cho mỗi câu hỏi

Kết quả chạy thật: bản C++ đúng 40/100 test (Subtask 1: 40/40, Subtask 2: 0/60); bản Python đúng 40/100 (Subtask 1: 40/40, Subtask 2: 0/60).

Cách 2Dùng công thức cho từng câu hỏi

Sàng các số nguyên tố tới $10^6$ một lần. Với mỗi câu hỏi $N$: duyệt các $p \le N$, tìm $k_p$ lớn nhất với $p^k \le N$; ghi $e_2, e_5$, còn các $p$ khác thì nhân $p^{k_p}$ vào phần dư (lấy dư cho $10$). Cuối cùng nhân thêm $2^{e_2 - e_5}$.

C++▶ Chạy tay từng dòng codeCách 2: với mỗi N, duyệt p ≤ N, tìm lũy thừa lớn nhất p^k ≤ N, nhân phần dư theo mod 10, bỏ các cặp (2, 5).

Dữ liệu vào (stdin) – sửa thoải mái6 5 4

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Đúng với mọi $N \le 10^6$ vì chỉ làm việc với số dư cho $10$, không bao giờ tràn.
• Nhưng mỗi câu hỏi duyệt tới $78\,498$ số nguyên tố ($\pi(10^6)$): với $10^6$ câu hỏi là $\approx 7{,}8 \cdot 10^{10}$ bước – quá chậm.

Không gian$O(V)$

Thời gian$O(V \log \log V + Q \cdot \pi(N))$

Kết quả chạy thật: bản C++ đúng 42/100 test (Subtask 1: 40/40, Subtask 2: 2/60); bản Python đúng 40/100 (Subtask 1: 40/40, Subtask 2: 0/60).

Cách 3Tính trước đáp án cho mọi N – Full điểm

Dùng quan sát cuối phần Ý tưởng: đi $N = 2, 3, \ldots, 10^6$, BCNN chỉ nhân thêm $p$ khi $N = p^k$. Ta đánh dấu trước ln[N] = p nếu $N$ là lũy thừa của số nguyên tố $p$, rồi cập nhật $e_2$, $e_5$, phần dư du và lưu ans[N]. Mỗi câu hỏi chỉ việc tra mảng. Lũy thừa $2^k \bmod 10$ (với $k \ge 1$) lặp theo chu kỳ $2, 4, 8, 6$ nên tra theo $k \bmod 4$.

C++▶ Chạy tay từng dòng codeCách 3 (minh hoạ tính trước tới 30): đi N từ 2, chỉ khi N = p^k mới cập nhật e2, e5 hoặc phần dư, lưu ans[N]; câu hỏi chỉ tra mảng.

Dữ liệu vào (stdin) – sửa thoải mái6 5 4

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Phần tính trước chạy $O(V \log \log V)$ (sàng) + $O(V)$ (đi một lượt), mỗi câu hỏi $O(1)$.
• Vì có tới $10^6$ dòng ra, C++ gom kết quả vào một string rồi in một lần; Python dùng sys.stdout.write một lần.
• Bản Python còn tăng tốc thêm: thay vì đi từng $N$, chỉ đi qua các mốc $p^k \le 10^6$ (khoảng $78\,700$ mốc, đã sắp tăng dần) và gán cả đoạn ans[truoc:q] bằng một phép gán lát cắt, vì giữa hai mốc liên tiếp đáp án không đổi.
• Không được lưu cả BCNN: chỉ cần $e_2$, $e_5$ và phần dư cho $10$ của phần còn lại (phần này luôn nguyên tố cùng nhau với $10$ nên lấy dư không làm mất thông tin chữ số cuối).

Không gian$O(V)$, $V = 10^6$

Thời gian$O(V \log \log V + Q)$

Kết quả chạy thật: bản C++ đúng 100/100 test, lâu nhất 0,198s; bản Python đúng 100/100 (Subtask 1: 40/40, Subtask 2: 60/60), lâu nhất 0,991s trong các test đúng.

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:

Lời giải	Subtask 1 ($N \le 50$) test 1–40	Subtask 2 test 41–100	Tổng	CPU lớn nhất (test đúng)
Cách 1 – C++	40/40	0/60	40/100	0,006s
Cách 1 – Python	40/40	0/60	40/100	0,035s
Cách 2 – C++	40/40	2/60	42/100	0,977s
Cách 2 – Python	40/40	0/60	40/100	0,198s
Cách 3 – C++	40/40	60/60	100/100	0,198s
Cách 3 – Python	40/40	60/60	100/100	0,991s

Ghi chú của mình: ba kỹ thuật đáng nhớ: (1) $\text{BCNN}(1..N)$ là tích các lũy thừa nguyên tố lớn nhất $\le N$; (2) "chữ số khác 0 cuối cùng" = bỏ các cặp $(2, 5)$ rồi lấy dư cho 10; (3) khi có rất nhiều câu hỏi trên miền nhỏ ($N \le 10^6$), hãy tính trước đáp án cho mọi $N$.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇