Trò chơi 2

Nguồn: CLUE OJ – Chương 46 Độ khó: Trung bình BCNN Đếm bội trong đoạn

Đề bài

Trong dịp liên hoan cuối năm, lớp của Khôi tổ chức trò chơi. Có hai đội chơi, Đội 1 có mã số là một số nguyên dương $x$, Đội 2 có mã số là một số nguyên dương $y$. Ban tổ chức trò chơi đưa ra hai số nguyên dương $m, n$ $(m \le n)$. Nhiệm vụ của mỗi đội là tìm số lượng số thuộc đoạn $[m; n]$ cùng chia hết cho mã số của cả hai đội. Ban tổ chức trò chơi muốn có đáp án chính xác của nhiệm vụ trên để kiểm tra kết quả của hai đội.

Yêu cầu: Viết chương trình giúp Ban tổ chức tìm số lượng số thuộc đoạn $[m; n]$ cùng chia hết cho $x, y$.

Dữ liệu vào: một dòng duy nhất chứa bốn số nguyên dương $m, n, x, y$ $(2 \le m, n \le 10^{12};\ 2 \le x, y \le 10^9)$, các số cách nhau bởi một dấu cách trống.

Kết quả: là số lượng số thỏa mãn yêu cầu bài toán.

Giới hạn:

• $60\%$ số test với $1 \le n - m \le 10^8$;
• $40\%$ số test với $10^8 < n - m \le 10^{12}$.

Thời gian 1 giây, bộ nhớ 256 MB.

Ví dụ – input

20 100 5 6

Ví dụ – output

3

Giải thích ví dụ: số chia hết cho cả 5 và 6 chính là số chia hết cho 30. Trong đoạn $[20; 100]$ có 3 số như vậy: $30, 60, 90$.

Lời mở đầu

"Chia hết cho cả $x$ và $y$" nghe như phải kiểm tra hai điều kiện, nhưng thật ra chỉ là một: chia hết cho BCNN của $x$ và $y$. Còn đếm số bội của một số trong một đoạn thì có công thức tính ngay, không cần duyệt. Mình đi từ cách duyệt từng số, tới duyệt theo bội, rồi tới công thức $O(\log)$.

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 + đếm bộiCách 1duyệt từng sốCách 2duyệt bội của maxCách 3công thức O(log)Tổ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 gồm 4 số. Đặt $L = \text{BCNN}(x, y)$:

Test	n − m	x, y	Đáp án	Ghi chú
1–20	20 – 88	2 – 15	0 – 33	10 test có $x = y$, 14 test có số này chia hết số kia
21–60	$1{,}1 \cdot 10^7$ – $9{,}7 \cdot 10^7$	16 – 119.670	15 – 90.563	$m$ có thể lớn tới $3{,}9 \cdot 10^{10}$
61–100	$2 \cdot 10^9$ – $10^{12}$	10 – 999.999.929	0 – 170.835.680	10 test có $L > 2^{31}$, 5 test có $L > n$ (đáp án 0)

• Test 1–60 đúng là nhóm $n - m \le 10^8$ (60%), test 61–100 là nhóm còn lại (40%).
• BCNN lớn nhất trong bộ test là $999\,999\,528\,000\,028\,471 \approx 10^{18}$ (test 99, $x = 999\,999\,599$, $y = 999\,999\,929$ nguyên tố cùng nhau) – vẫn vừa long long (tối đa $\approx 9{,}2 \cdot 10^{18}$).

Subtask	Điều kiện	Các test	Cách ăn được
1 (60%)	$n - m \le 10^8$	1 – 60	Cách 1 (sát nút), 2, 3
2 (40%)	$n - m \le 10^{12}$	61 – 100	Cách 3 (cách 2 ăn được phần lớn)

Ý tưởngChia hết cho cả x và y ⇔ chia hết cho BCNN

Một số chia hết cho cả $x$ và $y$ khi và chỉ khi nó là bội chung của $x$ và $y$, mà mọi bội chung đều là bội của BCNN:

Tính chất

$$x \mid t \ \text{và}\ y \mid t \quad\Longleftrightarrow\quad L \mid t, \qquad L = \text{BCNN}(x, y) = \frac{x}{\gcd(x, y)} \cdot y$$

Số bội của $L$ trong đoạn $[1; n]$ là $\lfloor n / L \rfloor$ (các bội $L, 2L, \ldots$). Đếm trong đoạn $[m; n]$ thì lấy hiệu như tổng tiền tố:

Đếm bội trong đoạn

$$\#\{t \in [m; n] : L \mid t\} = \left\lfloor \frac{n}{L} \right\rfloor - \left\lfloor \frac{m - 1}{L} \right\rfloor$$

Ví dụ: $L = 30$, $\lfloor 100/30 \rfloor - \lfloor 19/30 \rfloor = 3 - 0 = 3$. Em nhập 4 số (đoạn ngắn) rồi bấm Tiếp để xem:

m = n = x = y =

Ví dụ nhanh:

Cách 1Duyệt từng số trong đoạn

Duyệt $i$ từ $m$ tới $n$, đếm các số chia hết cho cả $x$ và $y$. Đơn giản, đúng, nhưng tốn đúng $n - m + 1$ vòng lặp.

C++▶ Chạy tay từng dòng codeCách 1: duyệt i từ m tới n, đếm i chia hết cho cả x và y.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Với $n - m \approx 10^8$, vòng lặp chạy $10^8$ lần, mỗi lần 1 – 2 phép chia lấy dư trên long long: khoảng 0,8 – 0,95 giây, rất sát giới hạn.
• Với $n - m$ tới $10^{12}$ thì không thể duyệt từng số.

Không gian$O(1)$

Thời gian$O(n - m)$

Kết quả chạy thật: bản C++ đúng 59/100 test (Subtask 1: 59/60, Subtask 2: 0/40). Test 23 ($n - m \approx 9{,}7 \cdot 10^7$) sát nút: lần chấm đầu quá 1 giây, chấm lại thì qua với 0,92 giây; nhiều test khác của subtask 1 chạy 0,8 – 0,97 giây. Bản Python chỉ đúng 20/100 (test 1–20 có đoạn ngắn).

Cách 2Chỉ duyệt các bội của số lớn hơn

Số cần đếm chắc chắn là bội của $\max(x, y)$. Nên chỉ cần nhảy theo các bội của số lớn: bắt đầu từ bội đầu tiên $\ge m$ là $\lceil m / x \rceil \cdot x$ (viết bằng số nguyên: (m + x - 1) / x * x), mỗi bước cộng $x$, rồi kiểm tra chia hết cho $y$.

C++▶ Chạy tay từng dòng codeCách 2: đổi để x ≥ y, nhảy theo bội của x từ bội đầu tiên ≥ m, kiểm tra chia hết cho y.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Số vòng lặp chỉ còn khoảng $(n - m) / \max(x, y)$. Ở subtask 1 thì rất nhanh; ở subtask 2, phần lớn test có $\max(x, y)$ đủ lớn nên vẫn kịp.
• Nhưng nếu $x, y$ nhỏ (ví dụ test 85: $n - m \approx 2{,}35 \cdot 10^{11}$, $\max(x,y) = 1879$) thì vẫn phải nhảy cỡ $10^8$ – $10^{10}$ bước → quá thời gian.

Không gian$O(1)$

Thời gian$O\big((n - m) / \max(x, y)\big)$

Kết quả chạy thật: bản C++ đúng 97/100 test (Subtask 1: 60/60, Subtask 2: 37/40 – quá thời gian ở test 77, 85, 89). Bản Python đúng 91/100 (test 91 sát nút: lần đầu qua với 0,99 giây, chấm lại thì quá giờ).

Cách 3BCNN + công thức đếm bội – Full điểm

Tính $L = x / \gcd(x, y) \cdot y$ (UCLN bằng Euclid) rồi in $\lfloor n/L \rfloor - \lfloor (m-1)/L \rfloor$. Không còn vòng lặp nào phụ thuộc độ dài đoạn.

C++▶ Chạy tay từng dòng codeCách 3: L = x / gcd(x, y) * y; đáp án n / L − (m − 1) / L.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Tính x / gcd * y (chia trước) thay vì x * y / gcd: ở đây $x \cdot y \le 10^{18}$ vẫn vừa long long, nhưng chia trước giúp số trung gian không bao giờ lớn hơn $L$.
• Khi $L > n$ (5 test), cả hai thương đều bằng 0 nên đáp án tự động là 0 – không cần xử lý riêng.

Không gian$O(1)$

Thời gian$O(\log \min(x, y))$

Kết quả chạy thật: bản C++ đúng 100/100 test, lâu nhất 0,007 giây; bản Python đúng 100/100, lâu nhất 0,037 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–60	Subtask 2 test 61–100	Tổng	CPU lớn nhất (test đúng)
Cách 1 – C++	59/60	0/40	59/100	0,928s
Cách 1 – Python	20/60	0/40	20/100	0,025s
Cách 2 – C++	60/60	37/40	97/100	0,817s
Cách 2 – Python	60/60	31/40	91/100	0,993s
Cách 3 – C++	60/60	40/40	100/100	0,007s
Cách 3 – Python	60/60	40/40	100/100	0,037s

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 nhiều test nhưng đều chạy sát giới hạn ở vài test (kết quả có thể dao động giữa các lần chấm). Cách 3 là lời giải chuẩn: hai kiến thức cần nhớ là chia hết cho cả x và y ⇔ chia hết cho BCNN và số bội của L trong [m; n] = [n/L] − [(m−1)/L].

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 😇