Bội chung nhỏ nhất

Nguồn: Tuyển sinh lớp 10 PTNK 2017–2018 Độ khó: Khá Map / Set Sàng nguyên tố

Đề bài

Bài 3: Bội chung nhỏ nhất

Bội số chung nhỏ nhất của các số dương $a_1, a_2, \ldots, a_m$ là số nguyên dương $K$ nhỏ nhất sao cho $K$ chia hết cho mọi số $a_1, a_2, \ldots, a_m$.

Yêu cầu: Với số nguyên dương $n$ cho trước, hãy tìm bội số chung nhỏ nhất $K$ của các số $1, 2, \ldots, n$. Vì số $K$ có thể rất lớn nên bạn chỉ đưa ra phần dư của phép chia $K$ cho $10^9 + 7$.

Dữ liệu: Vào từ file văn bản LCM.INP trong đó chứa duy nhất số $n$.

Kết quả: Ghi ra file văn bản LCM.OUT phần dư của phép chia $K$ cho $10^9 + 7$.

Giới hạn: $n \le 10^6$.

30% số test có $N \le 10^2$;
30% số test có $N \le 10^3$;
40% số test còn lại không có điều kiện gì thêm.

Lưu ý trên CLUE OJ: dữ liệu đọc từ file giống y như trong đề bài (LCM.INP / LCM.OUT). Ảnh đề gốc bị in mờ và ghi nhầm ở dòng "Kết quả" thành $10^3 + 9$ (có người đã sửa tay), đúng ra là $10^9 + 7$ như ở dòng "Yêu cầu" – bộ test cũng dùng $10^9 + 7$.

Ví dụ – input

Ví dụ – output

Lời mở đầu

Nghe tên bài thì quen: BCNN thì tính bằng UCLN, $\text{lcm}(a, b)$ $= \frac{a \cdot b}{\gcd(a, b)}$, làm lần lượt với $2, 3, \ldots, n$ là xong. Nhưng ở đây $K$ khổng lồ (với $n = 10^6$, $K$ có khoảng 434 nghìn chữ số!) nên bắt buộc phải lấy dư – và chính chỗ "lấy dư" làm cho công thức UCLN quen thuộc sai bét. Bài này dạy ta nhìn BCNN dưới góc độ thừa số nguyên tố, dùng map để lưu số mũ, rồi tối ưu bằng sàng Eratosthenes.

Bài yêu cầu đọc/ghi file nên trong code C++ mình dùng if (fopen("LCM.INP", "r")) { freopen(...); freopen(...); }: có file thì đọc/ghi file, không có thì vẫn dùng bàn phím/màn hình bình thường (tiện cho các bạn chạy thử).

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

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 OJ

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

Bộ test100 test, 3 subtask Cái bẫyUCLN + mod Ý tưởnglũy thừa nguyên tố Cách 1chia thử + map Cách 2sàng

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

Bộ test có 100 test, mỗi test chỉ là một số $n$:

Test	n nhỏ nhất	n lớn nhất	Subtask
1–15	1	15	1
16–30	24	99	1
31–60	113	862	2
61–70	3.249	9.580	3
71–80	12.494	39.014	3
81–99	105.269	132.124	3
100	1.000.000	1.000.000	3

15 test đầu là $n = 1, 2, \ldots, 15$ – vừa đủ nhỏ để $K$ chưa vượt $10^9 + 7$ (ví dụ $n = 15$ thì $K = 360360$). Những code sai kiểu "lấy dư lung tung" vẫn ăn được các test này.
Chỉ có đúng 1 test $n = 10^6$ (test 100), các test của subtask 3 còn lại có $n$ chỉ cỡ $10^4$ – $1{,}3 \cdot 10^5$.
Test $n = 1$: không có số nào ngoài số 1, đáp án là 1.

Đối chiếu subtask của đề với test thật (số test đúng của từng cách ở mỗi subtask):

Subtask	Điều kiện	Test	Cách 0 (UCLN + mod, sai)	Cách 1 C++ (chia thử + map)	Cách 1 Python (số lớn)	Cách 2 (sàng)
1 (30%)	$N \le 10^2$	1–30	15/30	30/30	30/30	30/30
2 (30%)	$N \le 10^3$	31–60	0/30	30/30	30/30	30/30
3 (40%)	$N \le 10^6$	61–100	0/40	40/40	20/40	40/40

Cái bẫyTính BCNN bằng UCLN rồi lấy dư – sai!

C++▶ Chạy tay từng dòng codeCách sai: BCNN bằng UCLN nhưng K đã bị lấy dư.

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

Dữ liệu mẫu:

Khung "Dữ liệu" so sánh K của code với BCNN thật (tính bằng số lớn).

Code này đúng khi $K$ còn nhỏ hơn $10^9 + 7$. Nhưng một khi $K$ đã bị lấy dư, __gcd(K, i) là UCLN của phần dư chứ không phải của $K$ thật. Ví dụ với $n = 24$: BCNN thật của $1..23$ là $5354228880$, chia hết cho 24 nên $\text{lcm}(\ldots, 24)$ không đổi. Nhưng phần dư của nó là $354228845$ – một số lẻ, UCLN với 24 bằng 1, thế là code nhân thêm 24 và hỏng từ đó. Phép lấy dư giữ được phép cộng, trừ, nhân, nhưng không giữ được phép chia và UCLN.

Kết quả chạy thật: bản C++ đúng 15/100 test (đúng test 1–15, sai/quá giờ test 16–100), chạy lâu nhất 0.099s. Đúng 15 test đầu ($n \le 15$) nhờ $K$ chưa kịp vượt $10^9 + 7$.

Ý tưởngBCNN = tích các lũy thừa nguyên tố lớn nhất

Viết mỗi số ra thừa số nguyên tố. Một số $K$ chia hết cho cả $1, 2, \ldots, n$ khi và chỉ khi với mỗi số nguyên tố $p$, số mũ của $p$ trong $K$ không nhỏ hơn số mũ của $p$ trong từng số. Vậy $K$ nhỏ nhất có số mũ của $p$ đúng bằng số mũ lớn nhất của $p$ trong các số $1..n$:

Công thức

$K = \prod_{p \le n,\ p \text{ nguyên tố}} p^{e_p}$ với $p^{e_p}$ là lũy thừa lớn nhất của $p$ không vượt quá $n$. Ví dụ $n = 10$: $K = 2^3 \cdot 3^2 \cdot 5 \cdot 7$ $= 8 \cdot 9 \cdot 5 \cdot 7$ $= 2520$.

Công thức chỉ có phép nhân, nên lấy dư thoải mái sau mỗi lần nhân. Vì sao số mũ lớn nhất của $p$ lại ứng với lũy thừa lớn nhất $\le n$? Vì chính số $p^{e}$ nằm trong $1..n$ khi $p^e \le n$, và không số nào $\le n$ chứa $p^{e+1}$ khi $p^{e+1} > n$.

Em nhập $n$ rồi bấm Tiếp để xem từng số nguyên tố "góp" lũy thừa lớn nhất của nó vào $K$ (ô vàng là số nguyên tố đang xét, ô xanh là các lũy thừa của nó, ô tím là số nguyên tố đã xét xong, ô gạch là hợp số đã bị sàng):

n =

Ví dụ nhanh:

Cách 1Phân tích từng số, map lưu số mũ lớn nhất

Cài đặt thẳng ý tưởng: duyệt $i = 2..n$, phân tích $i$ bằng cách chia thử, cập nhật mx[p] = max(mx[p], e). Cuối cùng nhân $p$ đúng mx[p] lần (lấy dư).

C++▶ Chạy tay từng dòng codeCách 1: phân tích từng số 2..n bằng chia thử, map mx lưu số mũ lớn nhất của mỗi số nguyên tố.

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

Dữ liệu mẫu:

Dùng map<int, int> mx: khoá là số nguyên tố, giá trị là số mũ lớn nhất gặp được. Map tự sắp xếp khoá tăng dần.
Vòng chia thử dừng khi $p \cdot p > x$; phần còn lại $x > 1$ là một số nguyên tố với số mũ 1.
Bản Python mình viết thêm theo kiểu "lười": Python có số nguyên lớn nên tính thẳng $K = \text{lcm}(K, i)$ chính xác, cuối cùng mới lấy dư. Đúng nhưng số $K$ càng lúc càng dài nên chậm dần.

Không gian$O(\pi(n))$ phần tử trong map

Thời gian$O(n \sqrt{n})$ trường hợp xấu (thực tế nhanh hơn nhiều)

Kết quả chạy thật: bản C++ đúng 100/100 test, chạy lâu nhất 0.848s; bản Python (số lớn) đúng 80/100 test (quá giờ ở test 81–100), lâu nhất trên 1s.

Cách 2Sàng Eratosthenes – Full điểm

Ta không cần phân tích từng số: theo công thức, chỉ cần biết các số nguyên tố $\le n$ và với mỗi $p$ nhân lũy thừa lớn nhất $q = p^e \le n$. Sàng Eratosthenes cho ta các số nguyên tố trong $O(n \log \log n)$.

C++▶ Chạy tay từng dòng codeCách 2: sàng Eratosthenes, mỗi số nguyên tố p nhân lũy thừa lớn nhất ≤ n.

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

Dữ liệu mẫu:

hop[p] == false khi tới lượt $p$ nghĩa là không số nguyên tố nhỏ hơn nào chia hết $p$ ⇒ $p$ nguyên tố. Ta gạch các bội của $p$ bắt đầu từ $p^2$ (các bội nhỏ hơn đã bị gạch bởi số nguyên tố nhỏ hơn).
j và q là long long vì $p \cdot p$ hoặc $q \cdot p$ có thể vượt int khi $p$ gần $10^6$.
K = K * q % MOD: $K < 10^9 + 7$ và $q \le 10^6$ nên tích không quá $10^{15}$, vừa long long.

Không gian$O(n)$

Thời gian$O(n \log \log n)$

Kết quả chạy thật: bản C++ đúng 100/100 test, chạy lâu nhất 0.006s; bản Python đúng 100/100 test, lâu nhất 0.21s.

Tổng kếtKết quả chạy thật trên bộ test

Cách	Ngôn ngữ	Đúng	Lâu nhất	Ghi chú
0. UCLN rồi lấy dư	C++	15/100	0.10s	Chỉ đúng test 1–15 (n ≤ 15) – sai từ n = 24
1. Chia thử + `map`	C++	100/100	0.85s	Đúng hết, nhưng test n = 10^6 khá sát giới hạn
1'. BCNN bằng số lớn	Python	80/100	> 1s	Test 81–100 quá thời gian
2. Sàng + lũy thừa lớn nhất	C++	100/100	0.01s	Full điểm, rất nhanh
	Python	100/100	0.21s	Full điểm

Ghi chú của mình: thời gian trong bảng là thời gian CPU đo trên máy của mình (giới hạn 1 giây). Cách 1 tuy đủ điểm trên bộ test này nhưng phần lớn thời gian dồn vào đúng test $n = 10^6$; nếu bộ test có nhiều test lớn hơn hoặc máy chấm yếu hơn thì rất dễ quá giờ. Cách 2 chạy chưa tới 0.01 giây. Nhớ: lấy dư được với phép nhân, không được với phép chia/UCLN!

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 😇

Lập Trình Thuật Toán