Sơn cọc tiêu (Đề tự luyện HSG Tin 9 – Bài 1)

Nguồn: Đề tự luyện HSG Tin học 9 – Bài 1 (đề tự soạn)Độ khó: DễBao hàm loại trừBCNNTràn sốMảng cộng dồn

Đề bài

Sơn cọc tiêu. Dọc bờ kênh xáng có hàng cọc tiêu đánh số $1, 2, 3, \dots$ Thầy Sơn chia học trò thành ba nhóm: nhóm Đỏ sơn mọi cọc có số chia hết cho $a$, nhóm Vàng sơn mọi cọc chia hết cho $b$, nhóm Xanh sơn mọi cọc chia hết cho $c$. Cọc được đúng một nhóm sơn thì có màu tươi; cọc bị từ hai nhóm trở lên sơn thì bị lem; cọc không ai sơn giữ màu xi măng. Thầy hỏi $Q$ câu: trong đoạn cọc từ $L$ đến $R$ có bao nhiêu cọc màu tươi?

Dữ liệu vào: dòng 1 là $a, b, c$ $(1 \le a, b, c \le 10^{18})$, có thể bằng nhau; dòng 2 là $Q$ $(1 \le Q \le 10^5)$; $Q$ dòng sau mỗi dòng là $L, R$ $(1 \le L \le R \le 10^{18})$.

Kết quả: $Q$ dòng, mỗi dòng là số cọc màu tươi của câu hỏi tương ứng.

• Subtask 1 (20%): $Q \le 10$, $R \le 10^6$.
• Subtask 2 (30%): $R \le 10^6$.
• Subtask 3 (50%): không ràng buộc thêm.

Input

2 3 5
2
1 10
11 29

Output

6
8

Giải thích

Đoạn $1..10$: cọc tươi là $2, 3, 4, 5, 8, 9$ (cọc $6$ và $10$ bị lem). Đoạn $11..29$: cọc tươi là $14, 16, 21, 22, 25, 26, 27, 28$.

Input

9 9 6
1
2 17

Output

2

Giải thích

Cọc $9$ được cả nhóm Đỏ và nhóm Vàng sơn nên bị lem. Trong đoạn $2..17$ chỉ cọc $6$ và $12$ là tươi.

Dành cho học viênNộp bài trên ClueOJ

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Bộ test có chia subtask và có cả những test "bẫy", nên code đúng ý tưởng nhưng sai chi tiết nhỏ cũng sẽ bị trừ điểm đó.

Nộp bài Sơn cọc tiêu

Lời mở đầu

Đây là bài "mở hàng" của đề nên ý tưởng không khó, nhưng thầy cài vào đó ba cái bẫy rất hay gặp trong các đề thi thật: đếm trên đoạn $[L, R]$ (dễ nhầm $L$ với $L-1$), "đúng một" khác với "ít nhất một", và tràn số khi tính bội chung nhỏ nhất của các số tới $10^{18}$.

Với mỗi cọc $i$, gọi $k(i)$ là số nhóm sơn cọc $i$, tức là số lượng số trong $\{a, b, c\}$ chia hết $i$. Cọc $i$ màu tươi khi và chỉ khi $k(i) = 1$. Hình dưới vẽ $30$ cọc đầu tiên với $a = 2, b = 3, c = 5$: ba hàng chấm phía trên cho biết nhóm nào sơn cọc đó.

Hình 1. Cọc có đúng một chấm to (k = 1) là cọc tươi; cọc có từ hai chấm to trở lên bị lem (gạch chéo). Từ 1 đến 30 có 14 cọc tươi.

Nhận xét quan trọng đầu tiên, dùng cho mọi cách: nếu gọi $F(n)$ là số cọc tươi trong đoạn $1..n$ thì số cọc tươi trong đoạn $[L, R]$ là

$$\text{đáp án} = F(R) - F(L-1).$$

Chú ý là trừ $F(L-1)$ chứ không phải $F(L)$, vì cọc số $L$ cũng nằm trong đoạn. Nhiều bạn quên chỗ này và mất điểm oan (xem bảng cuối bài).

Cách 1Duyệt từng cọc · 20%Cách 2Mảng cộng dồn · 50%Cách 3Bao hàm loại trừ · 100%

Cách 1Duyệt từng cọc – O(Q·(R − L)) · 20%

Làm đúng như đề kể: với mỗi câu hỏi, đi từ cọc $L$ tới cọc $R$, đếm xem cọc $i$ bị mấy nhóm sơn (kiểm tra $i \bmod a$, $i \bmod b$, $i \bmod c$), nếu đúng $1$ nhóm thì tăng biến đếm.

Với Subtask 1, mỗi câu hỏi duyệt tối đa $10^6$ cọc, có $10$ câu nên chỉ khoảng $10^7$ phép kiểm tra — chạy rất nhanh. Nhưng sang Subtask 2 có tới $10^5$ câu hỏi, mỗi câu dài cỡ $10^6$ cọc, tổng cộng $10^{11}$ phép — chắc chắn quá thời gian.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ll a, b, c;
    int q;
    cin >> a >> b >> c >> q;
    while (q--) {
        ll L, R;
        cin >> L >> R;
        ll dem = 0;
        for (ll i = L; i <= R; i++) {
            int k = 0;                  // so nhom son coc i
            if (i % a == 0) k++;
            if (i % b == 0) k++;
            if (i % c == 0) k++;
            if (k == 1) dem++;
        }
        cout << dem << '\n';
    }
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    a, b, c = int(data[0]), int(data[1]), int(data[2])
    q = int(data[3])
    out = []
    for t in range(q):
        L = int(data[4 + 2 * t])
        R = int(data[5 + 2 * t])
        dem = 0
        for i in range(L, R + 1):
            k = (i % a == 0) + (i % b == 0) + (i % c == 0)
            if k == 1:
                dem += 1
        out.append(dem)
    print('\n'.join(map(str, out)))

main()

Không gian$O(1)$

Thời gian$O(Q \cdot (R - L + 1))$

Cách 2Mảng cộng dồn – O(max R + Q) · 50%

Ở Subtask 2, các câu hỏi đều nằm trong $10^6$ cọc đầu tiên, chỉ là hỏi rất nhiều lần. Vậy ta tính trước một lần cho cả $10^6$ cọc:

$$pre[i] = pre[i-1] + \big[k(i) = 1\big], \qquad pre[0] = 0,$$

tức $pre[i] = F(i)$ là số cọc tươi trong đoạn $1..i$. Khi đó mỗi câu hỏi trả lời ngay bằng $pre[R] - pre[L-1]$ trong $O(1)$.

Ví dụ với $a=2, b=3, c=5$:

i	1	2	3	4	5	6	7	8	9	10
k(i)	0	1	1	1	1	2	0	1	1	2
pre[i]	0	1	2	3	4	4	4	5	6	6

Câu hỏi $[3, 9]$ có đáp án $pre[9] - pre[2] = 6 - 1 = 5$ (các cọc $3, 4, 5, 8, 9$). Đúng!

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXR = 1000000;
int pre[MAXR + 1];   // pre[i] = so coc mau tuoi trong 1..i
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll a, b, c;
    int q;
    cin >> a >> b >> c >> q;
    for (int i = 1; i <= MAXR; i++) {
        int k = (i % a == 0) + (i % b == 0) + (i % c == 0);
        pre[i] = pre[i - 1] + (k == 1);
    }
    while (q--) {
        ll L, R;
        cin >> L >> R;
        if (R > MAXR) R = MAXR;          // chi dung cho R <= 10^6
        if (L > R) { cout << 0 << '\n'; continue; }
        cout << pre[R] - pre[L - 1] << '\n';
    }
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    a, b, c = int(data[0]), int(data[1]), int(data[2])
    q = int(data[3])
    MAXR = 10 ** 6
    pre = [0] * (MAXR + 1)   # pre[i] = so coc mau tuoi trong 1..i
    for i in range(1, MAXR + 1):
        k = (i % a == 0) + (i % b == 0) + (i % c == 0)
        pre[i] = pre[i - 1] + (k == 1)
    out = []
    for t in range(q):
        L = int(data[4 + 2 * t])
        R = min(int(data[5 + 2 * t]), MAXR)   # chi dung cho R <= 10^6
        out.append(pre[R] - pre[L - 1] if L <= R else 0)
    print('\n'.join(map(str, out)))

main()

Không gian$O(\max R)$

Thời gian$O(\max R + Q)$

Vì sao chỉ được 50%?

Ở Subtask 3, $R$ lên tới $10^{18}$. Không máy tính nào có mảng $10^{18}$ phần tử, cũng không thể duyệt $10^{18}$ cọc trong 1 giây. Ta cần tính $F(n)$ không cần duyệt, chỉ bằng vài phép chia.

Cách 3Bao hàm loại trừ – O(Q) · 100%

Ta đã biết đếm số cọc chia hết cho $x$ trong đoạn $1..n$: đó là $\lfloor n / x \rfloor$. Cọc chia hết cho cả $a$ và $b$ chính là cọc chia hết cho $\text{BCNN}(a, b)$. Đặt

$$S_1 = \Big\lfloor \tfrac{n}{a} \Big\rfloor + \Big\lfloor \tfrac{n}{b} \Big\rfloor + \Big\lfloor \tfrac{n}{c} \Big\rfloor,\quad S_2 = \Big\lfloor \tfrac{n}{[a,b]} \Big\rfloor + \Big\lfloor \tfrac{n}{[a,c]} \Big\rfloor + \Big\lfloor \tfrac{n}{[b,c]} \Big\rfloor,\quad S_3 = \Big\lfloor \tfrac{n}{[a,b,c]} \Big\rfloor,$$

trong đó $[x, y]$ là BCNN. Câu hỏi là: ghép $S_1, S_2, S_3$ thế nào để được đúng số cọc có $k = 1$?

Mỗi cọc bị đếm bao nhiêu lần?

Xét một cọc bị đúng $k$ nhóm sơn. Trong $S_1$ nó được đếm $k$ lần (một lần cho mỗi nhóm). Trong $S_2$ nó được đếm bằng số cặp nhóm cùng sơn nó, tức $\binom{k}{2}$ lần. Trong $S_3$ nó được đếm $\binom{k}{3}$ lần. Ta tìm hệ số $x, y$ sao cho $S_1 - x S_2 + y S_3$ đếm mỗi cọc đúng $1$ lần nếu $k = 1$ và $0$ lần nếu $k \ne 1$:

k (số nhóm sơn)	lần trong $S_1$	lần trong $S_2$	lần trong $S_3$	$S_1 - 2S_2 + 3S_3$	Muốn
0	0	0	0	0	0
1	1	0	0	1	1
2	2	1	0	2 − 2 = 0	0
3	3	3	1	3 − 6 + 3 = 0	0

Hàng $k=2$ buộc $x = 2$, hàng $k = 3$ buộc $3 - 3\cdot 2 + y = 0$ nên $y = 3$. Vậy

$$F(n) = S_1 - 2S_2 + 3S_3.$$

Bẫy 1: "đúng một" khác "ít nhất một"

Công thức bao hàm loại trừ quen thuộc $S_1 - S_2 + S_3$ đếm số cọc được ít nhất một nhóm sơn (thử bảng trên: $k=2$ cho $1$, $k=3$ cho $1$). Đề hỏi cọc đúng một nhóm sơn nên hệ số phải là $1, -2, 3$. Bạn nào học thuộc lòng công thức mà không kiểm tra lại sẽ sai gần hết test. Một lỗi khác cũng hay gặp là nhớ đúng hệ số $-2$ nhưng để hệ số của $S_3$ là $1$: cả hai ví dụ của đề đều không có cọc nào bị cả ba nhóm sơn trong đoạn được hỏi, nên công thức sai này vẫn qua ví dụ.

Kiểm tra với $a=2, b=3, c=5, n=30$: $S_1 = 15+10+6 = 31$, $S_2 = 5+3+2 = 10$, $S_3 = 1$, nên $F(30) = 31 - 20 + 3 = 14$ — đúng bằng số cọc tươi đếm trong Hình 1. Còn khi $a = b$ (ví dụ 2), BCNN$(a,a) = a$ và công thức vẫn tự đúng, không cần xét riêng.

Mô phỏng dưới đây đi qua từng cọc, cộng phần đóng góp của nó vào $S_1, S_2, S_3$, để các bạn thấy tận mắt: cọc lem đóng góp $0$ vào $S_1 - 2S_2 + 3S_3$.

a b c n

Ví dụ nhanh:

Tính BCNN mà không bị tràn số

Ta có $\text{BCNN}(x, y) = \dfrac{x}{\text{UCLN}(x, y)} \cdot y$ (chia trước rồi mới nhân để số trung gian nhỏ). Nhưng với $x, y$ tới $10^{18}$, BCNN có thể lên tới $10^{36}$, vượt xa giới hạn của long long (khoảng $9{,}2 \cdot 10^{18}$). Khi tràn số, máy không báo lỗi mà lặng lẽ cho ra một số "rác".

Bẫy 2: tràn số khi tính BCNN

Lấy $a = 2^{32} = 4294967296$, $b = 2^{32} + 1$. Hai số nguyên tố cùng nhau nên BCNN thật là $2^{64} + 2^{32}$. Nhưng phép nhân long long chỉ giữ lại phần dư khi chia cho $2^{64}$, ra $2^{32} = 4294967296$! Chương trình sẽ tưởng có rất nhiều cọc chia hết cho cả $a$ và $b$, và in ra đáp án sai bét.

Cách sửa rất gọn: vì mọi $R \le 10^{18}$, một BCNN lớn hơn $10^{18}$ thì $\lfloor n / \text{BCNN} \rfloor$ luôn bằng $0$, ta chỉ cần biết nó "rất lớn" là đủ. Đặt $LIM = 2 \cdot 10^{18}$. Với $t = x / \text{UCLN}(x,y)$, nếu $t > LIM / y$ thì $t \cdot y > LIM$, ta trả về luôn $LIM$ mà không cần nhân. Phép so sánh $t > LIM / y$ chỉ dùng phép chia nên không bao giờ tràn. Khi đã "chặn" $[a,b] = LIM$ thì $[a,b,c] = \text{BCNN}(LIM, c)$ cũng được chặn về $LIM$ — vẫn đúng vì nó còn lớn hơn nữa.

Bẫy 3: kết quả cần long long

Với $a = 2, b = 3, c = 5$ và đoạn $[1, 10^{18}]$, đáp án cỡ $4{,}7 \cdot 10^{17}$ — dùng int là tràn ngay. Mọi biến đếm đều phải là long long.

Python thì có số nguyên lớn tuỳ ý nên không lo tràn; ta cứ tính BCNN thật (dù tới $10^{54}$) cũng không sao.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll LIM = 2000000000000000000LL; // 2e18 > moi R

ll bcnn(ll x, ll y) {
    ll g = __gcd(x, y);
    ll t = x / g;                       // bcnn = t * y
    if (t > LIM / y) return LIM;        // qua lon: coi nhu "vo cung"
    return t * y;
}

ll a, b, c, ab, ac, bc, abc;

ll F(ll n) { // so coc mau tuoi trong 1..n
    ll s1 = n / a + n / b + n / c;
    ll s2 = n / ab + n / ac + n / bc;
    ll s3 = n / abc;
    return s1 - 2 * s2 + 3 * s3;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> a >> b >> c;
    ab = bcnn(a, b); ac = bcnn(a, c); bc = bcnn(b, c);
    abc = bcnn(ab, c);
    int q;
    cin >> q;
    while (q--) {
        ll L, R;
        cin >> L >> R;
        cout << F(R) - F(L - 1) << '\n';
    }
    return 0;
}

import sys
from math import gcd

def main():
    data = sys.stdin.buffer.read().split()
    a, b, c = int(data[0]), int(data[1]), int(data[2])
    q = int(data[3])
    ab = a // gcd(a, b) * b          # Python khong bi tran so
    ac = a // gcd(a, c) * c
    bc = b // gcd(b, c) * c
    abc = ab // gcd(ab, c) * c

    def F(n):
        s1 = n // a + n // b + n // c
        s2 = n // ab + n // ac + n // bc
        s3 = n // abc
        return s1 - 2 * s2 + 3 * s3

    out = []
    for i in range(q):
        L = int(data[4 + 2 * i])
        R = int(data[5 + 2 * i])
        out.append(F(R) - F(L - 1))
    sys.stdout.write('\n'.join(map(str, out)) + '\n')

main()

Không gian$O(1)$

Thời gian$O(\log 10^{18} + Q)$

Khung dưới đây chạy tay đúng đoạn code C++ ở trên. Các bạn thử nút Bẫy tràn số để xem hàm bcnn "chặn" giá trị về $LIM$ như thế nào.

C++▶ Chạy tay từng dòng codeTính các BCNN (có chặn tràn số) rồi trả lời từng câu hỏi bằng F(R) − F(L − 1).

Dữ liệu vào (stdin) – sửa thoải mái2 3 5 2 1 10 11 29

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3typedef long long ll;

4const ll LIM = 2000000000000000000LL; // 2e18 > moi R

5

6ll bcnn(ll x, ll y) {

7 ll g = __gcd(x, y);

8 ll t = x / g; // bcnn = t * y

9 if (t > LIM / y) return LIM; // qua lon: coi nhu "vo cung"

10 return t * y;

11}

12

13ll a, b, c, ab, ac, bc, abc;

14

15ll F(ll n) { // so coc mau tuoi trong 1..n

16 ll s1 = n / a + n / b + n / c;

17 ll s2 = n / ab + n / ac + n / bc;

18 ll s3 = n / abc;

19 return s1 - 2 * s2 + 3 * s3;

20}

21

22int main() {

23 ios::sync_with_stdio(false);

24 cin.tie(nullptr);

25 cin >> a >> b >> c;

26 ab = bcnn(a, b); ac = bcnn(a, c); bc = bcnn(b, c);

27 abc = bcnn(ab, c);

28 int q;

29 cin >> q;

30 while (q--) {

31 ll L, R;

32 cin >> L >> R;

33 cout << F(R) - F(L - 1) << '\n';

34 }

35 return 0;

36}

ChậmVừaNhanhRất nhanh

Bộ test chấm "bắt" những lỗi nào?

Bộ test có 30 test: Subtask 1 có 8 test, Subtask 2 có 10 test (đều $Q$ lớn, đoạn dài gần $10^6$), Subtask 3 có 12 test (đều có $R$ cỡ $10^{17}$–$10^{18}$, nhiều test cố tình làm BCNN tràn số như $a = 2^{32}, b = 2^{32}+1$ hay $a = 3037000500, c = 3037000507$). Điểm tính theo từng test (thang 100%).

Cách làm	Sub 1 (8 test)	Sub 2 (10 test)	Sub 3 (12 test)	Điểm
Cách 1 – Duyệt từng cọc	Đúng 8/8	TLE 0/10	TLE 0/12	20
Cách 2 – Mảng cộng dồn	Đúng 8/8	Đúng 10/10	WA 0/12	50
Cách 3 – Bao hàm loại trừ (chuẩn)	Đúng 8/8	Đúng 10/10	Đúng 12/12	100
Sai: dùng công thức "ít nhất một" $S_1 - S_2 + S_3$	WA 1/8	WA 0/10	WA 2/12	10,8
Sai: tính BCNN x / g * y không chặn tràn số	Đúng 8/8	Đúng 10/10	WA 7/12	79,2
Sai: in $F(R) - F(L)$ thay vì $F(R) - F(L-1)$	WA 4/8	WA 1/10	WA 5/12	33,8
Sai: biến đếm trong $F$ dùng int	Đúng 8/8	Đúng 10/10	WA 3/12	62,5

Ghi chú của mình: các cách C++ ở trên đã được chấm thử với đúng bộ test của bài: Cách 1 đúng 8/8 test Subtask 1 và quá thời gian (chạy hơn 3 giây) ở toàn bộ 22 test còn lại; Cách 2 đúng 18/18 test của hai subtask đầu, sai cả 12 test Subtask 3; Cách 3 đúng 30/30 test, chạy lâu nhất khoảng 0,05 giây. Lời giải Python của Cách 3 cũng đúng 30/30 test, chạy dưới 0,4 giây ngay cả với CPython. Với các lời giải sai, điểm ở cột cuối là phần trăm số điểm của bài khi chấm theo từng test.

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 😇