Số đồng diễn (Đề tự luyện HSG Tin 9 – Bài 2) – Nhận xét p², p³, p·q, sàng nguyên tố và tổng tiền tố

Nguồn: Đề tự luyện HSG Tin học 9 – Bài 2 (đề tự soạn)Độ khó: Trung bìnhĐếm ướcSàng EratosthenesTổng tiền tố

Đề bài

Số đồng diễn. Nhóm $x$ học sinh được xếp thành đội hình chữ nhật $r$ hàng $\times$ $c$ em với $r \cdot c = x$, $2 \le r \le c$. Số $x$ là số đồng diễn nếu có đúng một đội hình như vậy (ví dụ $15$ là số đồng diễn: chỉ có $3 \times 5$; $12$ thì không: có $2 \times 6$ và $3 \times 4$; $7$ cũng không: không có đội hình nào). Trả lời $Q$ câu hỏi: trong đoạn $[L, R]$ có bao nhiêu số đồng diễn?

Dữ liệu vào: dòng đầu là $Q$ $(1 \le Q \le 2 \cdot 10^5)$; $Q$ dòng sau mỗi dòng hai số $L, R$ $(1 \le L \le R \le 10^7)$.

Kết quả: $Q$ dòng, mỗi dòng là số lượng số đồng diễn trong đoạn tương ứng.

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

Input

3
16 24
30 40
50 60

Output

2
5
4

Giải thích

$[16, 24]$: $21 = 3 \times 7$, $22 = 2 \times 11$. $[30, 40]$: $33, 34, 35, 38, 39$. $[50, 60]$: $51, 55, 57, 58$. Các số khác không có đội hình nào (số nguyên tố) hoặc có từ hai đội hình trở lên (như $16$: $2 \times 8$ và $4 \times 4$).

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ố đồng diễn

Lời mở đầu

Một đội hình $r \times c$ với $r \le c$ và $r \cdot c = x$ hoàn toàn được xác định bởi số hàng $r$: khi đó $c = x / r$. Điều kiện $r \le c$ tương đương $r \cdot r \le x$, tức $r \le \sqrt{x}$. Vậy:

Nhận xét 1

Số đội hình của $x$ = số ước $r$ của $x$ thoả mãn $2 \le r \le \sqrt{x}$.

Hình 1. Đội hình của 12, 8 và 9 học sinh: mỗi đội hình ứng với một ước $r \le \sqrt{x}$ ($r \ge 2$).

Hình trên cũng là cái bẫy của bài: nhiều bạn nhìn ví dụ ($21 = 3 \cdot 7$, $22 = 2 \cdot 11$, $33$, $34$, …) rồi đoán "số đồng diễn là tích hai số nguyên tố khác nhau" — thiếu mất $p^2$ (như $9$, $25$) và $p^3$ (như $8$, $27$)! Lộ trình:

Cách 1Đếm thẳng từng câu hỏi · 30%Cách 2Tính trước + cộng dồn · 60%Cách 3p², p³, p·q + sàng · 100%

Cách 1Đếm thẳng cho từng câu hỏi – O(Q · R · √R) · 30%

Viết hàm soCach(x) đếm số $r$ từ $2$ tới $\sqrt{x}$ (vòng lặp r * r <= x) mà $x$ chia hết cho $r$. Với mỗi câu hỏi, duyệt mọi $x$ từ $L$ đến $R$ và đếm các $x$ có soCach(x) == 1. Với $Q, R \le 1000$: khoảng $1000 \cdot 1000 \cdot 31 \approx 3 \cdot 10^7$ phép tính — ổn.

#include <bits/stdc++.h>
using namespace std;
int soCach(int x) {                    // so cach xep x ban thanh r hang, c cot (2 <= r <= c)
    int cnt = 0;
    for (int r = 2; r * r <= x; r++)
        if (x % r == 0) cnt++;         // r hang, x / r cot (x / r >= r)
    return cnt;
}
int main() {
    int q;
    cin >> q;
    while (q--) {
        int L, R;
        cin >> L >> R;
        int dem = 0;
        for (int x = L; x <= R; x++)
            if (soCach(x) == 1) dem++;
        cout << dem << "\n";
    }
    return 0;
}

import sys

def so_cach(x):                        # so cach xep x ban thanh r hang, c cot (2 <= r <= c)
    cnt = 0
    r = 2
    while r * r <= x:
        if x % r == 0:
            cnt += 1                   # r hang, x // r cot
        r += 1
    return cnt

def main():
    data = sys.stdin.read().split()
    q = int(data[0])
    out = []
    for k in range(q):
        L = int(data[1 + 2 * k]); R = int(data[2 + 2 * k])
        dem = 0
        for x in range(L, R + 1):
            if so_cach(x) == 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 \sqrt{R})$

Cách 2Tính trước cho mọi x rồi cộng dồn – O(R√R + Q) · 60%

Cách 1 tính đi tính lại soCach(x) cho cùng một $x$ ở nhiều câu hỏi. Ta tính một lần cho mọi $x$ từ $1$ tới $M = \max R$ và lập mảng cộng dồn: pre[x] = số số đồng diễn trong $[1, x]$. Khi đó câu hỏi $[L, R]$ có đáp án pre[R] - pre[L - 1] — chú ý là $L - 1$, không phải $L$, vì $L$ cũng nằm trong đoạn.

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> q;
    vector<int> L(q), R(q);
    int M = 1;
    for (int i = 0; i < q; i++) {
        cin >> L[i] >> R[i];
        M = max(M, R[i]);
    }
    vector<int> pre(M + 1, 0);           // pre[x] = so so chi co mot cach xep trong [1, x]
    for (int x = 1; x <= M; x++) {
        int cnt = 0;
        for (int r = 2; r * r <= x; r++)
            if (x % r == 0) cnt++;
        pre[x] = pre[x - 1] + (cnt == 1 ? 1 : 0);
    }
    for (int i = 0; i < q; i++) cout << pre[R[i]] - pre[L[i] - 1] << "\n";
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    q = int(data[0])
    qs = list(map(int, data[1:1 + 2 * q]))
    M = max(qs)
    pre = [0] * (M + 1)                  # pre[x] = so so chi co mot cach xep trong [1, x]
    for x in range(1, M + 1):
        cnt = 0
        r = 2
        while r * r <= x:
            if x % r == 0:
                cnt += 1
            r += 1
        pre[x] = pre[x - 1] + (1 if cnt == 1 else 0)
    out = []
    for k in range(q):
        out.append(pre[qs[2 * k + 1]] - pre[qs[2 * k] - 1])
    sys.stdout.write("\n".join(map(str, out)) + "\n")

main()

Không gian$O(M)$

Thời gian$O(M\sqrt{M} + Q)$

Vì sao vẫn chưa đủ?

Với $M = 10^7$, tổng các $\sqrt{x}$ là khoảng $\frac{2}{3} \cdot 10^{7} \cdot \sqrt{10^7} \approx 2 \cdot 10^{10}$ phép chia — quá chậm. Kể cả khi dừng vòng lặp ngay khi đã thấy $2$ đội hình thì các số nguyên tố (có hơn $6{,}6 \cdot 10^5$ số) vẫn phải chạy hết tới $\sqrt{x}$: bản thử của mình chạy hơn 60 giây.

Cách 3Nhận xét p², p³, p·q + sàng Eratosthenes – O(M log log M + Q) · 100%

Gọi $d(x)$ là số ước của $x$. Các ước của $x$ đi thành cặp $(r, x / r)$, trong mỗi cặp có một số $\le \sqrt{x}$. Nên số ước $\le \sqrt{x}$ là $\lceil d(x) / 2 \rceil$; bỏ đi ước $1$, số đội hình là $\lceil d(x)/2 \rceil - 1$. Vậy

đúng một đội hình $\iff \lceil d(x)/2 \rceil = 2 \iff d(x) = 3$ hoặc $d(x) = 4$.

Viết $x = p_1^{e_1} p_2^{e_2} \cdots$ thì $d(x) = (e_1 + 1)(e_2 + 1)\cdots$. Do đó:

• $d(x) = 3$: chỉ có thể là $3 = 3$, tức $x = p^2$ ($p$ nguyên tố). Đội hình duy nhất: $p \times p$.
• $d(x) = 4$: hoặc $4 = 4$ tức $x = p^3$ (đội hình $p \times p^2$), hoặc $4 = 2 \cdot 2$ tức $x = p \cdot q$ với $p < q$ nguyên tố (đội hình $p \times q$).

Kết luận

$x$ là số đồng diễn $\iff$ $x = p^2$, $x = p^3$ hoặc $x = p \cdot q$ ($p < q$ đều nguyên tố).

Thuật toán: dùng sàng Eratosthenes tìm mọi số nguyên tố $\le M$; với mỗi số nguyên tố $p$ mà $p^2 \le M$: đánh dấu $p^2$, $p^3$ (nếu $\le M$) và $p \cdot q$ cho mọi số nguyên tố $q > p$ với $p \cdot q \le M$. Mỗi số đồng diễn được đánh dấu đúng một lần. Số cặp $(p, q)$ chính bằng số các số dạng $p \cdot q \le M$ (khoảng $1{,}9 \cdot 10^6$ với $M = 10^7$), rất nhanh. Cuối cùng cộng dồn như Cách 2.

L R

Ví dụ nhanh:

Code hoàn chỉnh (Python dùng bytearray và phép gán đoạn để sàng nhanh, rồi gom các số đồng diễn vào một danh sách đã sắp xếp và trả lời bằng bisect — tương đương với mảng cộng dồn):

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> q;
    vector<int> L(q), R(q);
    int M = 1;
    for (int i = 0; i < q; i++) {
        cin >> L[i] >> R[i];
        M = max(M, R[i]);
    }
    vector<char> nt(M + 1, 1);                    // sang Eratosthenes: nt[x] = 1 neu x nguyen to
    nt[0] = nt[1] = 0;
    for (long long i = 2; i * i <= M; i++)
        if (nt[i])
            for (long long j = i * i; j <= M; j += i) nt[j] = 0;
    vector<int> ps;                               // danh sach so nguyen to <= M
    for (int i = 2; i <= M; i++)
        if (nt[i]) ps.push_back(i);
    vector<int> dem(M + 1, 0);                    // dem[x] = 1 neu x chi co dung mot cach xep
    for (int a = 0; a < (int)ps.size(); a++) {
        long long p = ps[a];
        if (p * p > M) break;
        dem[p * p] = 1;                           // x = p^2: chi co p x p
        if (p * p * p <= M) dem[p * p * p] = 1;   // x = p^3: chi co p x p^2
        for (int b = a + 1; b < (int)ps.size() && p * ps[b] <= M; b++)
            dem[p * ps[b]] = 1;                   // x = p * q (p < q): chi co p x q
    }
    for (int x = 1; x <= M; x++) dem[x] += dem[x - 1];   // cong don: dem[x] = so so tot trong [1, x]
    for (int i = 0; i < q; i++) cout << dem[R[i]] - dem[L[i] - 1] << "\n";
    return 0;
}

import sys
from bisect import bisect_left, bisect_right
from itertools import compress

def main():
    data = sys.stdin.buffer.read().split()
    q = int(data[0])
    qs = list(map(int, data[1:1 + 2 * q]))
    M = max(max(qs), 1)
    nt = bytearray([1]) * (M + 1)              # sang Eratosthenes: nt[x] = 1 neu x nguyen to
    nt[0] = 0; nt[1] = 0
    i = 2
    while i * i <= M:
        if nt[i]:
            nt[i * i::i] = bytes(len(range(i * i, M + 1, i)))
        i += 1
    ps = list(compress(range(M + 1), nt))      # danh sach so nguyen to <= M
    tot = []                                   # cac so chi co dung mot cach xep
    for a in range(len(ps)):
        p = ps[a]
        if p * p > M:
            break
        tot.append(p * p)                      # x = p^2
        if p * p * p <= M:
            tot.append(p * p * p)              # x = p^3
        b = bisect_right(ps, M // p)           # cac q nguyen to voi p < q va p * q <= M
        tot.extend([p * x for x in ps[a + 1:b]])
    tot.sort()
    out = []
    for k in range(q):
        l = qs[2 * k]; r = qs[2 * k + 1]
        out.append(bisect_right(tot, r) - bisect_left(tot, l))
    sys.stdout.write("\n".join(map(str, out)) + "\n")

main()

Không gian$O(M)$

Thời gian$O(M \log\log M + Q)$

C++▶ Chạy tay từng dòng codeSàng nguyên tố, đánh dấu p², p³, p·q, cộng dồn rồi trả lời câu hỏi.

Dữ liệu vào (stdin) – sửa thoải mái3 16 24 30 40 50 60

Dữ liệu mẫu:

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

2using namespace std;

3int main() {

4 ios::sync_with_stdio(false);

5 cin.tie(nullptr);

6 int q;

7 cin >> q;

8 vector<int> L(q), R(q);

9 int M = 1;

10 for (int i = 0; i < q; i++) {

11 cin >> L[i] >> R[i];

12 M = max(M, R[i]);

13 }

14 vector<char> nt(M + 1, 1); // sang Eratosthenes: nt[x] = 1 neu x nguyen to

15 nt[0] = nt[1] = 0;

16 for (long long i = 2; i * i <= M; i++)

17 if (nt[i])

18 for (long long j = i * i; j <= M; j += i) nt[j] = 0;

19 vector<int> ps; // danh sach so nguyen to <= M

20 for (int i = 2; i <= M; i++)

21 if (nt[i]) ps.push_back(i);

22 vector<int> dem(M + 1, 0); // dem[x] = 1 neu x chi co dung mot cach xep

23 for (int a = 0; a < (int)ps.size(); a++) {

24 long long p = ps[a];

25 if (p * p > M) break;

26 dem[p * p] = 1; // x = p^2: chi co p x p

27 if (p * p * p <= M) dem[p * p * p] = 1; // x = p^3: chi co p x p^2

28 for (int b = a + 1; b < (int)ps.size() && p * ps[b] <= M; b++)

29 dem[p * ps[b]] = 1; // x = p * q (p < q): chi co p x q

30 }

31 for (int x = 1; x <= M; x++) dem[x] += dem[x - 1]; // cong don: dem[x] = so so tot trong [1, x]

32 for (int i = 0; i < q; i++) cout << dem[R[i]] - dem[L[i] - 1] << "\n";

33 return 0;

34}

ChậmVừaNhanhRất nhanh

Cách khác cũng được 100%: sàng đếm ước

Nếu không nghĩ ra nhận xét $p^2, p^3, pq$, các em vẫn có thể tính $d(x)$ cho mọi $x \le M$ bằng cách "rải bội": với mỗi $i$ từ $1$ đến $M$, cộng $1$ vào d[i], d[2i], d[3i], …. Tổng số phép là $M(1 + \frac12 + \frac13 + \dots) \approx M \ln M \approx 1{,}6 \cdot 10^8$ — C++ vẫn chạy kịp. Sau đó số đồng diễn là các $x$ có $d(x) = 3$ hoặc $4$.

Những cái bẫy hay gặp

(1) Chỉ đếm $p \cdot q$ với $p < q$: quên $p^2$ (như $4 = 2 \times 2$, $9$, $25$). (2) Đếm "số nửa nguyên tố" $p \cdot q$ với $p \le q$ nhưng quên $p^3$ (như $8 = 2 \times 4$, $27 = 3 \times 9$). (3) Trả lời pre[R] - pre[L] thay vì pre[R] - pre[L - 1]. Ví dụ của đề cho cả ba lỗi này ra đúng 2 5 4!

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

Bộ test có 26 test: Subtask 1 có 8 test ($R \le 1000$: ví dụ, $[1, 1]$, các điểm $4, 8, 9, 25, 27, 125, 343, 961, \dots$, chia $[1, 1000]$ thành 100 khối, …), Subtask 2 có 8 test ($Q \approx 10^5$, $R$ tới $10^5$), Subtask 3 có 10 test ($Q \approx 2 \cdot 10^5$, $R$ tới $10^7$). Các kiểu câu hỏi: đoạn rất rộng, ngẫu nhiên, $L = R$ là $p^2, p^3, pq, p^4, p^2q$ hoặc số nguyên tố, đầu mút $L$ hay $R$ đúng bằng một số đặc biệt, lập phương và bình phương của số nguyên tố lớn gần $10^7$. Điểm tính theo từng test (thang 100%).

Cách làm	Sub 1 (8 test)	Sub 2 (8 test)	Sub 3 (10 test)	Điểm
Cách 1 – Đếm thẳng từng câu hỏi	Đúng 8/8	TLE 0/8	TLE 0/10	30
Cách 2 – Tính trước bằng √x + cộng dồn	Đúng 8/8	Đúng 8/8	TLE 0/10	60
Cách 3 – p², p³, p·q + sàng (chuẩn)	Đúng 8/8	Đúng 8/8	Đúng 10/10	100
Cách 2 có dừng sớm khi thấy 2 đội hình	Đúng 8/8	Đúng 8/8	TLE 0/10	60
Sai: chỉ đếm p·q với p < q	WA 2/8	WA 0/8	WA 0/10	7,5
Sai: đếm p·q và p² nhưng quên p³	WA 2/8	WA 0/8	WA 0/10	7,5
Sai: pre[R] - pre[L]	WA 2/8	WA 0/8	WA 0/10	7,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 (hơn 3 giây) ở toàn bộ 18 test còn lại; Cách 2 đúng 16/16 test của hai subtask đầu và quá thời gian cả 10 test Subtask 3; Cách 3 đúng 26/26 test, test lâu nhất chạy khoảng 0,24 giây. Lời giải Python của Cách 3 cũng đúng 26/26 test, chạy tối đa khoảng 1,45 giây với CPython. Mỗi test có hàng nghìn câu hỏi nên các lời giải sai chỉ "sống sót" được ở 2 test nhỏ nhất; còn ví dụ của đề thì cố tình chỉ chứa các số dạng $p \cdot q$ và đầu mút trái không phải số đồng diễn — nên cả ba lời giải sai đều vẫn ra đúng 2 5 4. Nhớ tự nghĩ thêm test nha!

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 😇