Modulo

Nguồn: Đề thi tuyển sinh lớp 10 TPHCM 2022 – 2023 (Bài 3) Độ khó: Trung bình Đồng dư UCLN – Euclid Ước số

Đề bài

Bình mới được học về phép toán modulo: $A \bmod B$ là số dư của phép chia $A$ cho $B$. Ví dụ $5 \bmod 2 = 1$ vì $5$ chia $2$ được thương $2$ dư $1$; $9 \bmod 3 = 0$ vì $9$ chia $3$ được thương $3$ dư $0$.

Cô giáo cho Bình một dãy số nguyên dương và yêu cầu tìm tất cả các số nguyên dương $M$ sao cho các phần tử trong dãy khi chia cho $M$ đều có cùng số dư.

Yêu cầu: cho trước một dãy số nguyên, hãy tìm các số nguyên dương $M > 1$ sao cho các số trong dãy khi chia cho $M$ luôn có cùng số dư.

Dữ liệu vào: dòng đầu là số nguyên $N$ $(2 \le N \le 100)$ – số phần tử của dãy. Mỗi dòng trong $N$ dòng tiếp theo chứa một phần tử của dãy, là số nguyên trong đoạn $[1, 10^9]$. Các phần tử trong dãy là phân biệt. Dữ liệu luôn đảm bảo có ít nhất một số $M$ thỏa mãn.

Kết quả: in trên một dòng các số $M$ theo thứ tự tăng dần, cách nhau một khoảng trắng.

Ràng buộc: $50\%$ số test có các giá trị trong dãy không quá $10\,000$.

Ví dụ 1 – input

4
24
36
48
96

Ví dụ 1 – output

2 3 4 6 12

Ví dụ 2 – input

3
5
17
23

Ví dụ 2 – output

2 3 6

Giải thích ví dụ 1: với $M = 12$: $24, 36, 48, 96$ đều chia hết cho $12$ (cùng dư $0$). Với $M = 5$: $24 \bmod 5 = 4$ nhưng $36 \bmod 5 = 1$ nên không được. Ví dụ 2 với $M = 6$: $5 \bmod 6 = 5$, $17 \bmod 6 = 5$, $23 \bmod 6 = 5$ – cùng dư $5$.

Lưu ý nộp bài: đề gốc đọc/ghi tệp MODULO.INP / MODULO.OUT, nhưng trên CLUE OJ bài này đọc từ bàn phím và in ra màn hình, nên code bên dưới dùng cin / cout bình thường.

Lời mở đầu

Đây là bài tập rất hay để thấy sức mạnh của đồng dư: thay vì thử từng $M$ (có thể tới gần $10^9$ giá trị), ta biến điều kiện "cùng số dư" thành "$M$ chia hết các hiệu", rồi gom tất cả các hiệu lại bằng UCLN. Bài toán khi đó chỉ còn là liệt kê ước của một số. Mình sẽ đi từ cách thử trực tiếp (ăn 50% điểm) tới cách chuẩn chạy tức thì.

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ưởngM chia hết các hiệuCách 1thử từng MCách 2UCLN + thử tới gCách 3UCLN + ước tới √gTổng kếtkết quả chạy thật

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

Bộ test có 100 test, mình đặt $g$ là UCLN của các hiệu $|a_i - a_1|$ (ý nghĩa của $g$ xem ở phần Ý tưởng):

Test	N	Giá trị nhỏ nhất – lớn nhất	max − min	$g$	Số đáp án $M$
1–20	2 – 10	2 … 548	4 – 540	4 – 20	2 – 5
21–50	100	1 … 9.999	6.824 – 9.996	4 – 20	2 – 5
51–80	100	2 … 602.888.340	44.717.620 – 602.888.280	4 – 20	2 – 5
81–100	100	4 … 400.816.295	88.359.920 – 400.803.580	8 – 100	2 – 8

• Test 1–50 có mọi giá trị $\le 10\,000$ đúng như ràng buộc $50\%$ của đề; test 51–100 có giá trị tới cỡ $6 \cdot 10^8$.
• Mọi test đều có các phần tử phân biệt, và luôn có ít nhất 2 đáp án (không test nào có $g$ là số nguyên tố). Test 100 có nhiều đáp án nhất: 2 4 5 10 20 25 50 100.
• Điểm đáng chú ý: ở mọi test, $g \le 100$ dù các số lên tới hàng trăm triệu. Điều này làm một cách "chưa chuẩn" (cách 2) vẫn qua hết test, mình sẽ nói kỹ ở dưới.

Subtask	Điều kiện	Các test	Cách ăn được
1 (50%)	giá trị $\le 10^4$	1 – 50	Cách 1, 2, 3
2 (50%)	giá trị $\le 10^9$	51 – 100	Cách 2 (nhờ $g$ nhỏ), Cách 3

Ý tưởngCùng số dư ⇔ M chia hết các hiệu

Nếu $x$ và $y$ chia cho $M$ có cùng số dư $r$, tức là $x = qM + r$ và $y = q'M + r$, thì $x - y = (q - q')M$ chia hết cho $M$. Ngược lại, nếu $M \mid (x - y)$ thì $x$ và $y$ có cùng số dư khi chia cho $M$. Đây chính là định nghĩa đồng dư:

Tính chất đồng dư

$$x \equiv y \pmod M \quad\Longleftrightarrow\quad M \mid (x - y)$$

Cả dãy cùng số dư khi chia cho $M$ ⇔ mọi phần tử cùng số dư với $a_1$ ⇔ $M$ chia hết tất cả các hiệu $a_2 - a_1, a_3 - a_1, \ldots, a_N - a_1$. Một số chia hết tất cả các số đó khi và chỉ khi nó chia hết UCLN của chúng:

Kết luận

$$g = \gcd\big(|a_2 - a_1|,\ |a_3 - a_1|,\ \ldots,\ |a_N - a_1|\big), \qquad M \text{ thỏa mãn} \Longleftrightarrow M > 1 \text{ và } M \mid g$$

Ví dụ 1: các hiệu so với $24$ là $12, 24, 72$, $g = \gcd(12, 24, 72) = 12$. Các ước lớn hơn $1$ của $12$ là $2, 3, 4, 6, 12$ – đúng đáp án. Ví dụ 2: hiệu là $12, 18$, $g = 6$ → $2, 3, 6$.

UCLN tính bằng thuật toán Euclid: $\gcd(a, b) = \gcd(b, a \bmod b)$, dừng khi $b = 0$. Lưu ý $\gcd(0, x) = x$ nên ta khởi tạo $g = 0$ rồi lần lượt "gộp" từng hiệu vào. Em nhập dãy số rồi bấm Tiếp để xem từng bước: tính các hiệu, gộp UCLN, rồi liệt kê ước của $g$:

Dãy số:

Ví dụ nhanh:

Vậy bài toán gồm 2 việc: tính $g$ (Euclid, rất nhanh) và liệt kê ước của $g$. Cách 1 dưới đây chưa dùng nhận xét này mà thử thẳng; cách 2 và cách 3 khác nhau ở chỗ liệt kê ước.

Cách 1Thử từng M, kiểm tra số dư của cả dãy

Làm đúng theo đề: thử lần lượt $M = 2, 3, \ldots$ và kiểm tra mọi $a_i \bmod M$ có bằng $a_1 \bmod M$ không. Thử tới đâu thì dừng? Nếu $M$ thỏa mãn thì $M$ chia hết hiệu $\max - \min$ (một số dương), nên $M \le \max - \min$. Vòng ngoài chạy tới $\max - \min$ là đủ.

C++▶ Chạy tay từng dòng codeCách 1: thử M = 2, 3, …, max − min; với mỗi M so số dư của từng a[i] với a[0].

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Vòng trong dùng break ngay khi gặp số khác dư, nên với phần lớn $M$ chỉ tốn 1 – 2 phép so sánh. Dù vậy vòng ngoài vẫn phải chạy đủ $\max - \min$ lần.
• Với giá trị $\le 10^4$ thì $\max - \min < 10^4$: chạy tức thì. Với giá trị cỡ $10^8 – 10^9$ thì vòng ngoài chạy hàng trăm triệu lần → quá 1 giây.
• Dùng long long cho m và các phần tử cho an toàn (hiệu tối đa gần $10^9$ vẫn vừa int, nhưng thói quen tốt khi làm việc với số lớn).

Không gian$O(N)$

Thời gian$O\big((\max - \min) \cdot N\big)$ – thực tế gần $O(\max - \min)$

Kết quả chạy thật: bản C++ đúng 53/100 test (Subtask 1: 50/50, Subtask 2: 3/50). 3 test lọt ở subtask 2 là test 63, 72, 80 – có $\max - \min \approx 4{,}5 \cdot 10^7$ nên chạy vừa kịp (0,78 – 0,89 giây); các test còn lại quá thời gian. Bản Python đúng 50/100 (chỉ subtask 1).

Cách 2Tính UCLN g rồi thử M từ 2 tới g

Áp dụng ý tưởng: tính $g = \gcd(|a_2 - a_1|, \ldots, |a_N - a_1|)$ bằng hàm gcd tự viết theo thuật toán Euclid, rồi in mọi $M$ từ $2$ tới $g$ mà $g \bmod M = 0$. Vì các ước được duyệt từ nhỏ đến lớn nên kết quả tự động tăng dần.

C++▶ Chạy tay từng dòng codeCách 2: gộp UCLN các hiệu bằng Euclid, rồi thử M từ 2 tới g.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Hàm gcd lặp: mỗi vòng thay $(a, b)$ bằng $(b, a \bmod b)$. Số vòng lặp chỉ cỡ $\log$ của số lớn (khoảng vài chục vòng với số $10^9$).
• llabs là trị tuyệt đối cho long long, vì $a_i - a_1$ có thể âm.
• Phần tính $g$ rất nhanh, nhưng vòng for(m = 2; m <= g; m++) chạy $g$ lần. Đề không giới hạn $g$: chẳng hạn dãy chỉ gồm $1$ và $10^9$ thì $g = 999\,999\,999$ và vòng này chạy gần $10^9$ phép chia lấy dư. Mình đo thử bản C++ với dữ liệu đó mất gần 9 giây (bản Python còn chậm hơn nhiều).

Vì sao cách 2 vẫn qua hết test?

Như đã thấy ở phần Bộ test, mọi test của CLUE đều có $g \le 100$, nên vòng thử ước chỉ chạy tối đa 100 lần. Đây là "may mắn" của bộ test chứ không phải độ phức tạp tốt. Đi thi gặp test có $g$ lớn là cách 2 bị quá thời gian, nên ta cần cách 3.

Không gian$O(N)$

Thời gian$O(N \log V + g)$, $V$ là giá trị lớn nhất

Kết quả chạy thật: bản C++ đúng 100/100 test, lâu nhất 0,009 giây; bản Python cũng 100/100, lâu nhất 0,027 giây (nhờ $g \le 100$ ở mọi test).

Cách 3UCLN + liệt kê ước theo cặp tới √g – Full điểm thật sự

Ước của $g$ luôn đi theo cặp $(d, g/d)$, và trong mỗi cặp có một số $\le \sqrt{g}$. Vì vậy chỉ cần duyệt $d$ từ $1$ tới $\sqrt{g}$: gặp $d \mid g$ thì lấy cả $d$ lẫn $g/d$ (cẩn thận khi $d = g/d$, tức $g$ là số chính phương, chỉ lấy một lần). Cuối cùng sắp xếp lại và bỏ số $1$.

C++▶ Chạy tay từng dòng codeCách 3: gộp UCLN các hiệu, liệt kê ước của g theo cặp (d, g/d) với d·d ≤ g, sắp xếp rồi in các ước > 1.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Vòng for(d = 1; d * d <= g; d++) chạy khoảng $\sqrt{g} \le 31\,623$ lần với $g < 10^9$ – không đáng kể. Với dữ liệu "$1$ và $10^9$" ở trên, cách 3 chạy chỉ 0,01 giây (so với gần 9 giây của cách 2).
• Số ước của một số $\le 10^9$ tối đa là $1344$, nên mảng ds rất nhỏ, sắp xếp tức thì.
• Dùng long long d để d * d không tràn số.

Không gian$O(N + \text{số ước của } g)$

Thời gian$O(N \log V + \sqrt{g})$

Kết quả chạy thật: bản C++ đúng 100/100 test, lâu nhất 0,005 giây; bản Python đúng 100/100, lâu nhất 0,028 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:

Lời giải	Subtask 1 test 1–50	Subtask 2 test 51–100	Tổng	CPU lớn nhất (test đúng)
Cách 1 – C++	50/50	3/50	53/100	0,891s
Cách 1 – Python	50/50	0/50	50/100	0,033s
Cách 2 – C++	50/50	50/50	100/100	0,009s
Cách 2 – Python	50/50	50/50	100/100	0,027s
Cách 3 – C++	50/50	50/50	100/100	0,005s
Cách 3 – Python	50/50	50/50	100/100	0,028s

Ghi chú của mình: cả 3 cách đều cho đáp án đúng ở mọi test chạy kịp. Cách 1 chỉ ăn chắc subtask 1. Cách 2 qua hết test nhờ bộ test có $g$ nhỏ, nhưng sẽ quá thời gian nếu $g$ lớn (gần 9 giây với $g \approx 10^9$). Cách 3 mới là lời giải chuẩn: $O(N \log V + \sqrt{g})$ cho mọi dữ liệu. Bài học rút ra: "cùng số dư" ⇔ "chia hết hiệu" – gặp lại rất nhiều trong các bài đồng dư.

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 😇