Trực nhật

Nguồn: Tin học trẻ bảng B – Huyện đoàn Gia Viễn 2023 – 2024 (Câu 1) Độ khó: Dễ UCLN – BCNN Thuật toán Euclid

Đề bài

Nam và Bình là đôi bạn thân học chung lớp. Trong lớp học thì tất cả các bạn đều phải trực nhật và cứ sau một số $x$ ngày nhất định thì bạn đó mới phải trực nhật lại. Biết rằng ban đầu Nam và Bình đều trực nhật ngày đầu tiên, và 2 bạn muốn biết sau bao nhiêu ngày thì 2 bạn lại trực nhật chung với nhau và khi đó mỗi bạn đã trực nhật bao nhiêu lần.

Yêu cầu: Em hãy lập trình để trả lời câu hỏi của Nam và Bình nhé.

Dữ liệu vào: đọc từ file TRUCNHAT.INP gồm 2 số nguyên $x_1, x_2$ $(2 \le x_1, x_2 \le 10^9)$ lần lượt là số ngày mà sau đó Nam và Bình mới phải trực nhật lại.

Dữ liệu ra: ghi ra file TRUCNHAT.OUT gồm:

• Dòng đầu tiên ghi ra số ngày Nam và Bình cùng nhau trực nhật lại;
• Dòng thứ 2 chứa 2 số lần lượt là số lần một bạn đã trực nhật cho tới lúc 2 bạn cùng trực nhật.

Giới hạn: thời gian 1 giây, bộ nhớ 256 MB.

Ví dụ – input

6 4

Ví dụ – output

12
2 3

Giải thích ví dụ: Nam trực lại sau mỗi 6 ngày (các mốc 6, 12, 18, …), Bình sau mỗi 4 ngày (4, 8, 12, …). Mốc chung đầu tiên là ngày thứ 12. Đến lúc đó Nam đã trực $12 / 6 = 2$ lần, Bình $12 / 4 = 3$ lần.

Lưu ý nộp bài: trên CLUE OJ bài này đọc/ghi qua tệp TRUCNHAT.INP / TRUCNHAT.OUT. Trong code mình dùng if (fopen("TRUCNHAT.INP", "r")) { freopen(...); freopen(...); }: có tệp thì đọc tệp, không có thì đọc bàn phím, nộp ở đâu cũng được.

Lời mở đầu

Ngày hai bạn trực chung là số vừa chia hết cho $x_1$ vừa chia hết cho $x_2$, nhỏ nhất – chính là bội chung nhỏ nhất (BCNN). Đề nghe rất dễ, nhưng với $x_1, x_2$ tới $10^9$ thì BCNN có thể lên tới cỡ $10^{17}$: cách "đếm từng ngày" sẽ chậm, và nếu dùng int thì còn bị tràn số. Mình đi từ cách mô phỏng, tới cách thử UCLN, rồi cách chuẩn dùng thuật toán Euclid.

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Ý tưởngBCNN = x₁·x₂ / UCLNCách 1đếm bội của x₁Cách 2thử UCLN giảm dầnCách 3EuclidTổng kếtkết quả chạy thật

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

Bộ test có 100 test, mỗi test chỉ gồm 2 số $x_1, x_2$. Các test không sắp theo độ khó mà xen kẽ lớn nhỏ. Mình thống kê lại (đặt $g = \gcd(x_1, x_2)$, $L$ là đáp án dòng 1):

Đặc điểm	Số test
Cả hai số $\le 1000$	18
Cả hai số $\le 10^6$	38
Số lớn nhất $\approx 5 \cdot 10^8$ (lớn nhất là $500\,030\,285$)	có ở rất nhiều test
$g = 1$ (hai số nguyên tố cùng nhau)	48
Một số chia hết số kia (đáp án là số lớn hơn)	11
Đáp án $L > 2^{31} - 1$ (dùng int là tràn số)	44
Đáp án lớn nhất	$250\,009\,217\,570\,594\,416 \approx 2{,}5 \cdot 10^{17}$

• $g$ trong bộ test luôn nhỏ (lớn nhất là 100), nên $L$ thường rất lớn, gần bằng $x_1 \cdot x_2$.
• Có 1 test chứa số $1$ (đề ghi $x \ge 2$ nhưng test vẫn có) – các cách bên dưới đều xử lý đúng.
• $L \le 2{,}5 \cdot 10^{17} < 9{,}2 \cdot 10^{18}$ nên long long chứa thoải mái.

Ý tưởngNgày trực chung là BCNN

Nam trực vào các ngày $x_1, 2x_1, 3x_1, \ldots$ (tính từ ngày đầu), Bình vào các ngày $x_2, 2x_2, \ldots$. Ngày đầu tiên hai dãy gặp nhau là số nhỏ nhất chia hết cho cả hai: $L = \text{BCNN}(x_1, x_2)$. Khi đó Nam đã trực $L / x_1$ lần, Bình $L / x_2$ lần.

Công thức

$$\text{BCNN}(x_1, x_2) = \frac{x_1 \cdot x_2}{\gcd(x_1, x_2)}$$

Còn UCLN tính bằng thuật toán Euclid: $\gcd(a, b) = \gcd(b, a \bmod b)$, dừng khi $b = 0$ (lúc đó đáp án là $a$). Mỗi bước số nhỏ đi rất nhanh, chỉ vài chục bước là xong với số $10^9$.

Em nhập $x_1, x_2$ rồi bấm Tiếp để xem lịch trực của hai bạn (với số nhỏ) và các bước Euclid:

x₁ = x₂ =

Ví dụ nhanh:

Cách 1Đi lần lượt các ngày Nam trực, chờ trùng ngày Bình

Cách "nghe sao làm vậy": xét lần lượt các ngày Nam trực $t = x_1, 2x_1, 3x_1, \ldots$; ngày đầu tiên mà $t$ chia hết cho $x_2$ chính là ngày trực chung. Không cần biết gì về UCLN.

C++▶ Chạy tay từng dòng codeCách 1: cộng dồn t += x1 cho tới khi t chia hết cho x2.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Số vòng lặp đúng bằng (số lần Nam trực) $- 1 = L / x_1 - 1 = x_2 / g - 1$. Nếu hai số nguyên tố cùng nhau và $x_2 \approx 5 \cdot 10^8$ thì vòng lặp chạy cỡ $5 \cdot 10^8$ lần, mỗi lần có một phép chia lấy dư – sát hoặc quá 1 giây.
• Bắt buộc dùng long long cho t: ở 44 test, $t$ vượt quá $2^{31} - 1$.
• Mẹo nhỏ: nếu đi theo bội của số lớn hơn thì số vòng lặp chỉ còn $\min(x_1, x_2) / g$ – nhanh hơn nhiều nhưng vẫn không chắc chắn.

Không gian$O(1)$

Thời gian$O(x_2 / g)$

Kết quả chạy thật: bản C++ đúng 95/100 test; 5 test bị quá thời gian (test 21, 47, 52, 85, 97 – đều có $x_2 / g$ từ $1{,}7 \cdot 10^8$ tới $5 \cdot 10^8$), và nhiều test khác chạy sát nút 0,8 – 0,98 giây. Bản Python đúng 73/100.

Cách 2Thử UCLN từ min(x₁, x₂) giảm dần

Dùng công thức $L = x_1 \cdot x_2 / \gcd(x_1, x_2)$, nhưng tìm UCLN "thủ công": thử $g = \min(x_1, x_2)$, nếu chưa chia hết cả hai thì giảm $g$ đi 1. Số đầu tiên chia hết cả hai chính là UCLN.

C++▶ Chạy tay từng dòng codeCách 2: giảm g từ min(x1, x2) tới khi g chia hết cả hai số, rồi L = x1 / g * x2.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Số lần giảm $g$ là $\min(x_1, x_2) - g$. Khi hai số đều cỡ $5 \cdot 10^8$ và nguyên tố cùng nhau, vòng lặp chạy gần $5 \cdot 10^8$ lần, mỗi lần 2 phép chia lấy dư.
• Viết x1 / g * x2 (chia trước, nhân sau) để số trung gian không vượt quá $L$. Ở bài này $x_1 \cdot x_2 \le 10^{18}$ vẫn vừa long long, nhưng chia trước là thói quen tốt.

Không gian$O(1)$

Thời gian$O(\min(x_1, x_2))$

Kết quả chạy thật: bản C++ đúng 99/100 test, chỉ quá thời gian ở test 52 ($x_1 = 500\,013\,008$, $x_2 = 500\,005\,427$, nguyên tố cùng nhau – phải giảm $g$ hơn 500 triệu lần); vài test khác chạy sát 0,9 giây. Bản Python đúng 87/100.

Cách 3Thuật toán Euclid – Full điểm

Thay vòng thử bằng thuật toán Euclid: lặp $(a, b) \to (b, a \bmod b)$ tới khi $b = 0$. Mỗi 2 bước thì số lớn ít nhất giảm một nửa, nên chỉ tốn khoảng $2\log_2(10^9) \approx 60$ bước trong trường hợp xấu nhất.

C++▶ Chạy tay từng dòng codeCách 3: tính UCLN bằng hàm gcd (Euclid), rồi BCNN = x1 / g * x2.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Với test khó nhất (test 52: $500\,013\,008$ và $500\,005\,427$) Euclid chỉ cần vài chục bước – em thử bấm mẫu "Số lớn" ở khung chạy tay để thấy.
• Từ C++17 có sẵn hàm std::gcd (thư viện <numeric>) và Python có math.gcd, nhưng tự viết hàm Euclid giúp em hiểu bản chất.

Không gian$O(1)$

Thời gian$O(\log \min(x_1, x_2))$

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,035 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	Số test đúng	Lỗi	CPU lớn nhất (test đúng)
Cách 1 – C++	95/100	5 test quá thời gian	0,975s
Cách 1 – Python	73/100	27 test quá thời gian	0,717s
Cách 2 – C++	99/100	1 test quá thời gian	0,956s
Cách 2 – Python	87/100	13 test quá thời gian	0,247s
Cách 3 – C++	100/100	–	0,005s
Cách 3 – Python	100/100	–	0,035s

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 và cách 2 qua được rất nhiều test vì phần lớn test có số nhỏ hoặc có UCLN lớn, nhưng chạy sát nút ở các test mà hai số cỡ $5 \cdot 10^8$ – chỉ cần máy chấm chậm hơn một chút là mất điểm. Cách 3 (Euclid) mới là lời giải chuẩn: $O(\log)$, chạy tức thì với mọi dữ liệu. Đừng quên long long: 44/100 test có đáp án vượt quá phạm vi int.

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 😇