Chuyên đề 6: Số học trong đề thi với C++ và Python: đếm bội trong đoạn, bao hàm
Lời mở đầu
Ở bài 12: Số học cơ bản em đã có đủ “đồ nghề”: phép chia lấy dư, liệt kê ước trong $O(\sqrt{n})$, thuật toán Euclid, sàng Eratosthenes và phân tích thừa số nguyên tố. Nhưng khi vào phòng thi, đề hiếm khi hỏi thẳng “tìm ƯCLN của a và b”. Đề hay hỏi kiểu: đếm các số trong đoạn $[a, b]$ chia hết cho 3 hoặc 5 với $b = 10^{18}$, số nào trong $[1, 10^6]$ có nhiều ước nhất, BCNN của $10^5$ số, hay số có 100000 chữ số có chia hết cho 7 không. Dùng vòng lặp ngây thơ thì quá thời gian, còn dùng sai kiểu dữ liệu thì tràn số.
Chuyên đề này không giảng lại bài 12 mà đi thẳng vào các dạng bài đó: công thức đếm, bẫy số âm, bẫy tràn số, kỹ thuật sàng ước. Em nên nắm chắc bài 12, bài 13: Mảng cộng dồn (dùng lại ở phần bài tập), chuyên đề 2 (chia làm tròn xuống, căn bậc hai chính xác) và chuyên đề 3: Số nguyên lớn trước khi đọc tiếp.
Lộ trình bài viết, bấm vào từng phần để nhảy tới:
Phần 1Đếm số chia hết cho k trong đoạn và bao hàm – loại trừ
Câu hỏi khởi động: trong đoạn $[1, n]$ có bao nhiêu số chia hết cho $k$? Các bội của $k$ là $k, 2k, 3k, \ldots$ và bội cuối cùng không vượt $n$ là $\lfloor n / k \rfloor \cdot k$. Vậy có đúng $\lfloor n / k \rfloor$ số. Ví dụ trong $[1, 100]$ có $\lfloor 100 / 7 \rfloor = 14$ số chia hết cho 7. Không cần vòng lặp nào cả!
Với đoạn $[a, b]$ bất kỳ, ta dùng ý tưởng giống mảng cộng dồn ở bài 13: số bội trong $[a, b]$ = số bội trong “$(-\infty, b]$” trừ số bội trong “$(-\infty, a - 1]$”:
$$\text{cnt}(a, b, k) = \left\lfloor \frac{b}{k} \right\rfloor - \left\lfloor \frac{a-1}{k} \right\rfloor$$
Công thức này đúng với mọi $a \le b$, kể cả số âm, với điều kiện $\lfloor \ \rfloor$ là chia làm tròn xuống. Và đây chính là cái bẫy: phép / của C++ làm tròn về 0, không phải làm tròn xuống.
| Đoạn, k | Đúng (làm tròn xuống) | C++ viết b / k - (a - 1) / k | Các bội thật sự |
|---|---|---|---|
| $[1, 100]$, $k = 7$ | $14 - 0 = 14$ | $14 - 0 = 14$ | 7, 14, …, 98 |
| $[10, 30]$, $k = 4$ | $7 - 2 = 5$ | $7 - 2 = 5$ | 12, 16, 20, 24, 28 |
| $[-7, 10]$, $k = 3$ | $3 - (-3) = 6$ | $3 - (-2) = 5$ ✗ | −6, −3, 0, 3, 6, 9 |
| $[-9, -4]$, $k = 5$ | $-1 - (-2) = 1$ | $0 - (-2) = 2$ ✗ | −5 |
Bảng 1. Với đoạn chứa số âm, phép / của C++ cho kết quả sai. Python dùng // là làm tròn xuống sẵn nên luôn đúng.
long long floorDiv(long long a, long long b){ // b > 0
long long q = a / b;
if(a % b < 0) q--; // a âm và không chia hết: C++ đã làm tròn LÊN, trừ 1
return q;
}
long long cnt(long long a, long long b, long long k){
return floorDiv(b, k) - floorDiv(a - 1, k);
}floorDiv em đã gặp ở chuyên đề 2. Python chỉ cần b // k - (a - 1) // k. Đừng quên số 0 chia hết cho mọi $k$: đoạn $[-7, 10]$ có số 0 trong danh sách bội.Bao hàm – loại trừ với hai số
Đề hỏi: trong $[1, 30]$ có bao nhiêu số chia hết cho 4 hoặc cho 6? Gọi $A$ là tập bội của 4 ($|A| = 7$), $B$ là tập bội của 6 ($|B| = 5$). Cộng $7 + 5 = 12$ là sai, vì 12 và 24 nằm trong cả hai tập, bị đếm hai lần. Ta phải trừ phần giao:
$$|A \cup B| = |A| + |B| - |A \cap B|$$
Một số chia hết cho cả 4 và 6 khi và chỉ khi nó chia hết cho BCNN(4, 6) = 12, không phải cho $4 \cdot 6 = 24$. Có $\lfloor 30 / 12 \rfloor = 2$ số như thế, nên đáp án là $7 + 5 - 2 = 10$. Nếu dùng nhầm 24, em được $7 + 5 - 1 = 11$, sai! Tích chỉ đúng khi hai số nguyên tố cùng nhau (như 3 và 5). Em bấm từng bước để thấy những số bị đếm trùng:
Ba số và hình Venn
Với ba tập, mỗi số trong giao của hai tập bị cộng 2 lần nên phải trừ đi; nhưng số nằm trong cả ba tập bị cộng 3 lần rồi bị trừ 3 lần, thành ra không được đếm lần nào, nên phải cộng lại:
$$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$$
Quy luật chung: cộng các tập lẻ, trừ các giao chẵn, “lẻ cộng, chẵn trừ”. Ví dụ đếm các số trong $[1, 30]$ chia hết cho 2, 3 hoặc 5:
Hình 1. Số trong mỗi vùng của hình Venn. Cộng tất cả các vùng bên trong ba vòng tròn được $8 + 4 + 2 + 4 + 2 + 1 + 1 = 22$, khớp với công thức bao hàm – loại trừ.
Bài này có một hệ quả hay dùng: số các số không chia hết cho số nào trong $x, y, z$ bằng tổng số phần tử trừ đi hợp. Ở hình 1, có $30 - 22 = 8$ số không chia hết cho 2, 3, 5, đó là 1, 7, 11, 13, 17, 19, 23, 29. Code dưới đây đếm các số trong $[a, b]$ ($-10^{18} \le a \le b \le 10^{18}$) chia hết cho ít nhất một trong $x, y, z \le 10^{18}$:
Xem code C++ / Python: đếm số chia hết cho x, y hoặc z trong đoạn [a, b] (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 4000000000000000000LL; // "vô cùng": lớn hơn hẳn mọi |a|, |b| <= 10^18
ll floorDiv(ll a, ll b){ // chia làm tròn XUỐNG (b > 0), đúng cả khi a âm
ll q = a / b;
if(a % b < 0) q--;
return q;
}
ll cnt(ll a, ll b, ll k){ // số bội của k trong đoạn [a, b]
return floorDiv(b, k) - floorDiv(a - 1, k);
}
ll lcmCap(ll x, ll y){ // BCNN(x, y); nếu vượt 2.10^18 thì trả về INF
if(x >= INF || y >= INF) return INF;
x /= __gcd(x, y); // chia trước rồi mới nhân
if(x > 2000000000000000000LL / y) return INF;
return x * y;
}
int main(){
ll a, b, x, y, z;
cin >> a >> b >> x >> y >> z;
ll xy = lcmCap(x, y), xz = lcmCap(x, z), yz = lcmCap(y, z), xyz = lcmCap(xy, z);
ll ans = cnt(a, b, x) + cnt(a, b, y) + cnt(a, b, z)
- cnt(a, b, xy) - cnt(a, b, xz) - cnt(a, b, yz)
+ cnt(a, b, xyz);
cout << ans;
return 0;
}from math import gcd
def cnt(a, b, k): # số bội của k trong [a, b]; // của Python đã làm tròn xuống
return b // k - (a - 1) // k
def lcm(x, y): # số nguyên Python không tràn
return x // gcd(x, y) * y
a, b, x, y, z = map(int, input().split())
xy, xz, yz = lcm(x, y), lcm(x, z), lcm(y, z)
xyz = lcm(xy, z)
ans = (cnt(a, b, x) + cnt(a, b, y) + cnt(a, b, z)
- cnt(a, b, xy) - cnt(a, b, xz) - cnt(a, b, yz)
+ cnt(a, b, xyz))
print(ans)long long. Nhưng nếu BCNN lớn hơn $2 \cdot 10^{18}$ thì trong đoạn $[a, b]$ chỉ có thể có nhiều nhất một bội của nó, đó là số 0 (nếu đoạn chứa 0). Nên ta thay BCNN bằng một số “vô cùng” INF = 4·10^18: công thức floorDiv vẫn đếm đúng số 0 đó. Để phát hiện tràn, kiểm tra x > LIM / y trước khi nhân, đừng nhân xong rồi mới kiểm tra (lúc đó đã tràn rồi). Ở phần 4 ta dùng lại đúng mẹo này.Phần 2Số chính phương, số lập phương và căn nguyên chính xác
Số chính phương là số có dạng $t^2$: $0, 1, 4, 9, 16, \ldots$ Đếm số chính phương trong $[1, n]$ thật dễ: $t^2 \le n \iff t \le \sqrt{n}$, nên có đúng $\lfloor \sqrt{n} \rfloor$ số. Trong đoạn $[a, b]$ (với $a \ge 1$) lại dùng phép trừ quen thuộc: $\lfloor \sqrt{b} \rfloor - \lfloor \sqrt{a - 1} \rfloor$.
Cái khó nằm ở chỗ tính $\lfloor \sqrt{n} \rfloor$ chính xác khi $n$ tới $10^{18}$. Ở chuyên đề 2 em đã biết sqrt trả về số thực và có thể sai lệch, nên phải sửa bằng hai vòng while. Số lập phương $t^3$ cũng vậy, với cbrt. Ta gom thành hai hàm dùng mãi:
long long isqrt_(long long n){ // lớn nhất r: r*r <= n
long long r = sqrtl((long double)n);
while(r * r > n) r--;
while((r + 1) * (r + 1) <= n) r++;
return r;
}
long long icbrt_(long long n){ // lớn nhất r: r*r*r <= n
long long r = cbrtl((long double)n);
while(r * r * r > n) r--;
while((r + 1) * (r + 1) * (r + 1) <= n) r++;
return r;
}math.isqrt(n) chính xác tuyệt đối; căn bậc ba thì tự viết theo cùng khuôn “lấy gần đúng rồi sửa”.Vừa chính phương vừa lập phương. Đề thi thích hỏi: có bao nhiêu số trong $[a, b]$ là số chính phương hoặc số lập phương? Lại là bao hàm – loại trừ! Phần giao là các số vừa là $u^2$ vừa là $v^3$. Nhìn phân tích thừa số: mọi số mũ phải chia hết cho 2 và cho 3, tức là chia hết cho 6. Vậy giao chính là các số dạng $t^6$.
Đếm $t^6 \le n$ cũng không cần hàm căn bậc sáu: $t^6 \le n \iff t^3 \le \lfloor \sqrt{n} \rfloor$, nên số lượng là icbrt_(isqrt_(n)). Ví dụ trong $[1, 100]$:
| Loại số | Các số trong [1, 100] | Công thức | Số lượng |
|---|---|---|---|
| Chính phương $t^2$ | 1, 4, 9, 16, 25, 36, 49, 64, 81, 100 | $\lfloor \sqrt{100} \rfloor$ | 10 |
| Lập phương $t^3$ | 1, 8, 27, 64 | $\lfloor \sqrt[3]{100} \rfloor$ | 4 |
| Cả hai: $t^6$ | 1, 64 | $\lfloor \sqrt[3]{\lfloor \sqrt{100} \rfloor} \rfloor = \lfloor \sqrt[3]{10} \rfloor$ | 2 |
| Chính phương hoặc lập phương | $10 + 4 - 2$ | 12 |
Bảng 2. Đếm số chính phương, lập phương trong $[1, 100]$ bằng công thức.
Xem code C++ / Python: đếm số chính phương, lập phương trong đoạn [a, b] tới 10^18 (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll isqrt_(ll n){ // lớn nhất r: r*r <= n
ll r = sqrtl((long double)n);
while(r * r > n) r--; // sửa sai số của sqrt
while((r + 1) * (r + 1) <= n) r++;
return r;
}
ll icbrt_(ll n){ // lớn nhất r: r*r*r <= n
ll r = cbrtl((long double)n);
while(r * r * r > n) r--;
while((r + 1) * (r + 1) * (r + 1) <= n) r++;
return r;
}
ll sq(ll n){ return isqrt_(n); } // số chính phương trong [1, n]
ll cb(ll n){ return icbrt_(n); } // số lập phương trong [1, n]
ll six(ll n){ return icbrt_(isqrt_(n)); } // số dạng t^6 trong [1, n]
int main(){
ll a, b;
cin >> a >> b;
ll s = sq(b) - sq(a - 1), c = cb(b) - cb(a - 1), t = six(b) - six(a - 1);
cout << s << " " << c << " " << t << " " << s + c - t;
return 0;
}from math import isqrt
def icbrt(n): # lớn nhất r: r**3 <= n
r = round(n ** (1 / 3))
while r ** 3 > n:
r -= 1
while (r + 1) ** 3 <= n:
r += 1
return r
def six(n): # số dạng t^6 trong [1, n]
return icbrt(isqrt(n))
a, b = map(int, input().split())
s = isqrt(b) - isqrt(a - 1)
c = icbrt(b) - icbrt(a - 1)
t = six(b) - six(a - 1)
print(s, c, t, s + c - t)Số có lẻ ước chính là số chính phương
Một nhận xét rất hay xuất hiện trong đề thi dưới dạng “bài toán đèn”. Ước của $n$ luôn đi theo cặp $(d, n / d)$: với $n = 12$ có các cặp $(1, 12), (2, 6), (3, 4)$, tổng 6 ước. Một cặp chỉ “gộp làm một” khi $d = n / d$, tức là $d^2 = n$. Vì thế:
- $n$ không chính phương: mọi ước đều có cặp, số ước chẵn;
- $n$ chính phương: có đúng một ước $\sqrt{n}$ đứng một mình, số ước lẻ. Ví dụ $36$: $(1, 36), (2, 18), (3, 12), (4, 9)$ và $6$ đứng một mình, tổng 9 ước.
Bài toán đèn: có $n$ bóng đèn đều tắt. Người thứ $i$ ($i = 1..n$) bấm công tắc của mọi đèn có số thứ tự chia hết cho $i$. Cuối cùng đèn nào sáng? Đèn số $j$ bị bấm đúng bằng số ước của $j$ lần, sáng khi bị bấm lẻ lần, tức là $j$ chính phương. Đáp án là $\lfloor \sqrt{n} \rfloor$, dù $n = 10^{18}$ (bài tập 2).
Phần 3Sàng ước: đếm ước và tổng ước cho nhiều số
Bài 12 dạy em liệt kê ước của một số trong $O(\sqrt{n})$. Nhưng nếu đề hỏi số ước của mọi số từ 1 đến $10^6$ (chẳng hạn tìm số có nhiều ước nhất, hay trả lời $10^5$ câu hỏi), làm từng số tốn khoảng $10^6 \cdot 1000 = 10^9$ phép tính, quá chậm.
Mẹo là đảo câu hỏi: thay vì hỏi “$j$ có những ước nào?”, ta hỏi “$i$ là ước của những số nào?”. Câu trả lời rất đơn giản: của $i, 2i, 3i, \ldots$ Vậy với mỗi $i$, ta đi qua tất cả bội của $i$ và cộng 1 vào bộ đếm ước của chúng (và cộng $i$ vào tổng ước). Cách làm này giống hệt sàng Eratosthenes, chỉ khác là ta cộng dồn thay vì gạch bỏ.
for(int i = 1; i <= N; i++)
for(int j = i; j <= N; j += i){ // j là bội của i => i là ước của j
d[j]++; // số ước
s[j] += i; // tổng ước (nhớ dùng long long)
}uoc[j].push_back(i), hay tính ước lớn nhất khác $j$.Vì sao nhanh? Với mỗi $i$, vòng trong chạy $\lfloor N / i \rfloor$ lần. Tổng số phép cộng là
$$\frac{N}{1} + \frac{N}{2} + \frac{N}{3} + \cdots + \frac{N}{N} = N \left(1 + \frac{1}{2} + \cdots + \frac{1}{N}\right) \approx N \ln N$$
Với $N = 10^6$ chỉ khoảng $1{,}4 \cdot 10^7$ phép cộng, chạy trong vài chục mili giây. Em chạy tay với $n$ nhỏ để thấy từng bội được cộng:
| Cách làm | Độ phức tạp | Số phép tính với $N = 10^6$ | Kết luận |
|---|---|---|---|
| Duyệt mọi $i$ từ 1 tới $j$ cho từng $j$ | $O(N^2)$ | $5 \cdot 10^{11}$ | quá chậm |
| Duyệt ước tới $\sqrt{j}$ cho từng $j$ (bài 12) | $O(N\sqrt{N})$ | $\approx 6{,}7 \cdot 10^8$ | chậm, dễ quá giờ |
| Sàng ước: cộng vào các bội | $O(N \log N)$ | $\approx 1{,}4 \cdot 10^7$ | nhanh |
Bảng 3. So sánh các cách tính số ước cho mọi số từ 1 tới $N$.
Bài mẫu: có $Q$ câu hỏi, mỗi câu cho $x \le 10^6$, in số ước và tổng các ước của $x$. Ta sàng một lần cho mọi số rồi trả lời mỗi câu trong $O(1)$:
Xem code C++ / Python: sàng số ước và tổng ước tới 10^6 (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
const int MAXV = 1000000;
int d[MAXV + 1];
long long s[MAXV + 1];
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
for(int i = 1; i <= MAXV; i++) // sàng ước: i là ước của i, 2i, 3i, ...
for(int j = i; j <= MAXV; j += i){
d[j]++;
s[j] += i;
}
int q;
cin >> q;
while(q--){
int x;
cin >> x;
cout << d[x] << " " << s[x] << "\n";
}
return 0;
}import sys
data = sys.stdin.buffer.read().split()
q = int(data[0])
xs = [int(v) for v in data[1:1 + q]]
M = max(xs) # chỉ sàng tới số lớn nhất được hỏi
d = [0] * (M + 1)
s = [0] * (M + 1)
for i in range(1, M + 1): # sàng ước: i là ước của i, 2i, 3i, ...
for j in range(i, M + 1, i):
d[j] += 1
for i in range(1, M + 1):
for j in range(i, M + 1, i):
s[j] += i
print('\n'.join(f"{d[x]} {s[x]}" for x in xs))Đếm ước từ phân tích thừa số nguyên tố
Khi $n$ lớn (tới $10^{12}$) mà chỉ có một vài số, ta phân tích $n = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}$ như bài 12. Một ước của $n$ có dạng $p_1^{f_1} \cdots p_k^{f_k}$ với mỗi $f_i$ chọn từ $0$ đến $e_i$, tức là $e_i + 1$ cách chọn cho mỗi số nguyên tố. Nhân lại:
$$d(n) = (e_1 + 1)(e_2 + 1) \cdots (e_k + 1), \qquad \sigma(n) = \prod_{i=1}^{k} \left(1 + p_i + p_i^2 + \cdots + p_i^{e_i}\right)$$
| $n$ | Phân tích | Số ước $d(n)$ | Tổng ước $\sigma(n)$ |
|---|---|---|---|
| 12 | $2^2 \cdot 3$ | $3 \cdot 2 = 6$ | $(1+2+4)(1+3) = 28$ |
| 36 | $2^2 \cdot 3^2$ | $3 \cdot 3 = 9$ (lẻ: chính phương) | $7 \cdot 13 = 91$ |
| 360 | $2^3 \cdot 3^2 \cdot 5$ | $4 \cdot 3 \cdot 2 = 24$ | $15 \cdot 13 \cdot 6 = 1170$ |
| 97 | $97$ (nguyên tố) | $2$ | $1 + 97 = 98$ |
Bảng 4. Số ước và tổng ước tính từ phân tích thừa số.
Xem code C++ / Python: số ước và tổng ước của n ≤ 10^12 bằng phân tích thừa số (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ll n;
cin >> n;
ll cntDiv = 1, sumDiv = 1;
for(ll p = 2; p * p <= n; p++){
if(n % p) continue;
int e = 0;
ll term = 1, pw = 1; // term = 1 + p + p^2 + ... + p^e
while(n % p == 0){
n /= p; e++;
pw *= p; term += pw;
}
cntDiv *= (e + 1);
sumDiv *= term;
}
if(n > 1){ // còn lại một thừa số nguyên tố lớn, mũ 1
cntDiv *= 2;
sumDiv *= (1 + n);
}
cout << cntDiv << " " << sumDiv;
return 0;
}n = int(input())
cnt_div, sum_div = 1, 1
p = 2
while p * p <= n:
if n % p == 0:
e, term, pw = 0, 1, 1 # term = 1 + p + p^2 + ... + p^e
while n % p == 0:
n //= p
e += 1
pw *= p
term += pw
cnt_div *= e + 1
sum_div *= term
p += 1
if n > 1: # còn lại một thừa số nguyên tố lớn, mũ 1
cnt_div *= 2
sum_div *= 1 + n
print(cnt_div, sum_div)e[p], cuối cùng nhân các $(e[p] + 1)$ lại (thường lấy dư cho $10^9 + 7$, xem bài 26: Toán modulo). Để phân tích nhanh nhiều số, dùng sàng ước nguyên tố nhỏ nhất spf[x]: khi đó tách $x$ chỉ mất $O(\log x)$ phép chia. Bài tập 7 luyện đúng kỹ thuật này.Phần 4ƯCLN, BCNN của cả dãy và bẫy tràn số
ƯCLN và BCNN đều có tính kết hợp: $\gcd(a, b, c) = \gcd(\gcd(a, b), c)$, BCNN cũng vậy. Nên ƯCLN của cả dãy chỉ là một vòng lặp “gộp dần”, giống cách tính tổng. Mẹo nhỏ: khởi tạo $g = 0$ vì $\gcd(0, x) = x$, và $l = 1$ vì $\text{BCNN}(1, x) = x$.
Với BCNN phải cẩn thận hai lần:
- Chia trước, nhân sau: viết
l / gcd(l, x) * xchứ không viếtl * x / gcd(l, x). Cách sau tính tích $l \cdot x$ trước nên tràn sớm hơn rất nhiều. - BCNN tăng rất nhanh: BCNN của các số từ 1 đến 50 đã vượt $3 \cdot 10^{20}$. Nếu đề yêu cầu “in -1 nếu BCNN vượt $10^{18}$”, phải kiểm tra trước khi nhân: $t \cdot x > 10^{18} \iff t > \lfloor 10^{18} / x \rfloor$.
Em chạy tay đoạn code sau, nhất là ví dụ “tràn” với ba số nguyên tố gần $10^9$:
Xem code C++ / Python: ƯCLN và BCNN của cả dãy, in -1 nếu BCNN vượt 10^18 (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll LIM = 1000000000000000000LL; // 10^18
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n;
cin >> n;
ll g = 0, l = 1;
bool over = false; // BCNN đã vượt 10^18 chưa?
for(int i = 0; i < n; i++){
ll x;
cin >> x;
g = __gcd(g, x); // ƯCLN(0, x) = x
if(over) continue;
ll t = l / __gcd(l, x); // CHIA TRƯỚC
if(t > LIM / x) over = true; // t * x > LIM <=> t > LIM / x
else l = t * x;
}
cout << g << "\n";
if(over) cout << -1; else cout << l;
return 0;
}import sys
from math import gcd
data = sys.stdin.buffer.read().split()
n = int(data[0])
LIM = 10 ** 18
g, l, over = 0, 1, False
for v in data[1:1 + n]:
x = int(v)
g = gcd(g, x) # gcd(0, x) = x
if not over:
l = l // gcd(l, x) * x
if l > LIM: # dừng sớm, kẻo số càng ngày càng dài
over = True
print(g)
print(-1 if over else l)__gcd(a, b) có ở mọi trình biên dịch GCC; từ C++17 có thêm gcd(a, b) và lcm(a, b) (nhưng lcm có sẵn vẫn tràn như thường). Python: math.gcd, và từ Python 3.9 có math.lcm(*a) nhận nhiều số. Số nguyên Python không tràn, nhưng BCNN của $10^5$ số có thể dài hàng trăm nghìn chữ số, phép tính trên số khổng lồ đó rất chậm. Vì vậy code Python ở trên cũng dừng sớm khi vượt $10^{18}$.ƯCLN tiền tố – hậu tố: bỏ đi một phần tử
Dạng bài quen thuộc: bỏ đi đúng một phần tử của dãy để ƯCLN các phần tử còn lại lớn nhất. Thử bỏ từng phần tử rồi tính lại ƯCLN mất $O(n^2)$. Hãy làm giống mảng cộng dồn ở bài 13, nhưng với phép $\gcd$ thay cho phép cộng:
pre[i]= ƯCLN của $a_1..a_i$ (tiền tố),suf[i]= ƯCLN của $a_i..a_n$ (hậu tố), vớipre[0] = suf[n+1] = 0;- bỏ $a_i$ thì ƯCLN phần còn lại là $\gcd(\text{pre}[i-1], \text{suf}[i+1])$.
| i | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| $a_i$ | 12 | 15 | 18 | 7 |
| pre[i] | 12 | 3 | 3 | 1 |
| suf[i] | 1 | 1 | 1 | 7 |
| bỏ $a_i$: $\gcd(\text{pre}[i-1], \text{suf}[i+1])$ | $\gcd(0, 1) = 1$ | $\gcd(12, 1) = 1$ | $\gcd(3, 7) = 1$ | $\gcd(3, 0) = 3$ |
Bảng 5. Bỏ số 7 thì ƯCLN phần còn lại lớn nhất, bằng 3.
Phần 5Chia hết với số rất lớn, dấu hiệu chia hết, tổng chữ số lặp
Khi đề cho một số có tới $10^5$ chữ số, em phải đọc nó vào xâu. Ở chuyên đề 3 em đã biết cách tính số dư của số lớn cho số nhỏ: đọc từng chữ số từ trái sang phải và chỉ giữ số dư r = (r * 10 + c) % k. Em xem lại cho thật rõ bằng mô phỏng:
Bẫy khi $k$ lớn. Nếu $k$ chỉ tới $10^9$ thì $r \cdot 10 + 9 < 10^{10}$, long long chứa thoải mái. Nhưng nếu đề cho $k$ tới $10^{18}$ thì $r$ có thể gần $10^{18}$ và $r \cdot 10$ gần $10^{19}$, vượt giới hạn $9{,}2 \cdot 10^{18}$ của long long! Cách chữa: khai báo $r$ là __int128 (số nguyên 128 bit của GCC) hoặc unsigned long long (tới $1{,}8 \cdot 10^{19}$). Python thì không lo tràn, nhưng có một bẫy khác: từ Python 3.11, int(s) với xâu dài hơn 4300 chữ số sẽ báo lỗi (ValueError), nên cũng nên đọc từng chữ số.
Dấu hiệu chia hết: khi nào chỉ cần nhìn vài chữ số?
| Chia hết cho | Dấu hiệu | Vì sao | Ví dụ |
|---|---|---|---|
| 2, 5, 10 | chữ số cuối | $10$ chia hết cho 2, 5 | 12345 ⋮ 5 |
| 4, 25 | số tạo bởi 2 chữ số cuối | $100$ chia hết cho 4, 25 | 987652 ⋮ 4 |
| 8, 125 | số tạo bởi 3 chữ số cuối | $1000$ chia hết cho 8, 125 | 12344 ⋮ 8 |
| 3, 9 | tổng các chữ số | $10 \equiv 1 \pmod 9$ | $1+2+3+4+5 = 15$ ⋮ 3 |
| 11 | tổng xen kẽ dấu từ chữ số cuối | $10 \equiv -1 \pmod{11}$ | $918082$: $2 - 8 + 0 - 8 + 1 - 9 = -22$ ⋮ 11 |
| 6, 12, 15, 18… | tách thành các số nguyên tố cùng nhau | $12 = 3 \cdot 4$ | ⋮ 12 ⟺ ⋮ 3 và ⋮ 4 |
Bảng 6. Các dấu hiệu chia hết. Với số dạng xâu, mỗi dấu hiệu chỉ cần vài phép tính trên chữ số.
Tất cả đều xuất phát từ một ý: viết số dưới dạng $\overline{d_1 d_2 \ldots d_m} = d_1 \cdot 10^{m-1} + \cdots + d_m$, rồi xem $10^j$ chia $k$ dư bao nhiêu. Với $k = 9$, mọi $10^j$ chia 9 dư 1, nên số chia 9 dư bằng tổng chữ số chia 9 dư. Cẩn thận với dòng cuối bảng: “chia hết cho 12 khi chia hết cho 2 và 6” là sai (thử số 6), vì 2 và 6 không nguyên tố cùng nhau; phải tách $12 = 3 \cdot 4$.
Tổng chữ số lặp
Đề kinh điển: cộng các chữ số của $n$, được số mới lại cộng chữ số tiếp, cho tới khi còn một chữ số. Ví dụ $98765 \to 35 \to 8$. Vì mỗi lần cộng chữ số thì số dư khi chia 9 không đổi, kết quả chính là $n \bmod 9$, chỉ khác là khi chia hết cho 9 thì được 9 (trừ $n = 0$). Công thức gọn:
$$\text{root}(n) = \begin{cases} 0 & n = 0 \\ 1 + (n - 1) \bmod 9 & n > 0 \end{cases}$$
Kiểm tra: $1 + 98764 \bmod 9 = 1 + 7 = 8$. Với số dạng xâu, ta lấy tổng chữ số (một số nhỏ) rồi áp dụng công thức. Code dưới đây đọc số $N$ (tới $10^5$ chữ số) và $k \le 10^{18}$, in $N \bmod k$ và tổng chữ số lặp của $N$:
- Đếm bội trong đoạn có số âm mà dùng
/của C++ (phần 1). - Lấy giao của bội $x$ và bội $y$ bằng tích $x \cdot y$ thay vì BCNN.
- Tính
l * x / gcd(nhân trước) làm BCNN tràn số; hoặc kiểm tra tràn sau khi đã nhân. - Dùng
(int)sqrt(n)với $n$ tới $10^{18}$ mà không sửa bằngwhile. - Mảng tổng ước khai báo
intkhi $N$ lớn, hay sàng tới $10^7$ mà quên giới hạn bộ nhớ. - Quên trường hợp $n = 0$, $n = 1$: số 0 chia hết cho mọi số, số 1 chỉ có 1 ước, tổng chữ số lặp của 0 là 0.
Xem code C++ / Python: số lớn chia lấy dư cho k tới 10^18 và tổng chữ số lặp (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int main(){
string s;
long long k;
cin >> s >> k;
__int128 r = 0; // r * 10 có thể tới ~10^19: vượt long long!
int sum = 0;
for(char c : s){
r = (r * 10 + (c - '0')) % k;
sum += c - '0';
}
int root = (sum == 0) ? 0 : 1 + (sum - 1) % 9; // tổng chữ số lặp
cout << (long long)r << "\n" << root;
return 0;
}import sys
data = sys.stdin.read().split()
s, k = data[0], int(data[1])
r, total = 0, 0
for c in s: # không dùng int(s): Python 3.11+ giới hạn 4300 chữ số
r = (r * 10 + ord(c) - 48) % k
total += ord(c) - 48
root = 0 if total == 0 else 1 + (total - 1) % 9 # tổng chữ số lặp
print(r)
print(root)- Tặng Quà (QUA) (HSG 12 Nam Định 2021 – 2022) (Dễ)
- Chia Quà (CHIAQUA) (Dễ)
- Đổi 1 Chữ Số Để Chia Hết Cho 3 (Dễ)
- Cắt Bìa (HSG9 TP Đà Nẵng 2018-2019 – Bài 2) (Dễ)
- Tìm số d lớn nhất để a % d = b % d = c % d (Trung bình)
- Ước Lớn Nhất (BESTUOC) (Trung bình)
- Chia Hết (CHIAHET) (Khá)
Bài tậpLuyện số học trong đề thi
Cho ba số nguyên $a$, $b$, $k$ ($-10^{18} \le a \le b \le 10^{18}$, $1 \le k \le 10^{18}$). Đếm số các số nguyên $x$ thuộc đoạn $[a, b]$ chia hết cho $k$.
-7 10 36📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
floorDiv, Python dùng //. Mẫu: $\lfloor 10/3 \rfloor = 3$, $\lfloor -8/3 \rfloor = -3$, đáp án $3 - (-3) = 6$, gồm $-6, -3, 0, 3, 6, 9$. Nếu viết (a - 1) / k trong C++ em sẽ được $-2$ và ra 5, sai.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll floorDiv(ll a, ll b){ // làm tròn xuống, b > 0
ll q = a / b;
if(a % b < 0) q--;
return q;
}
int main(){
ll a, b, k;
cin >> a >> b >> k;
cout << floorDiv(b, k) - floorDiv(a - 1, k);
return 0;
}a, b, k = map(int, input().split())
print(b // k - (a - 1) // k)Hành lang có $n$ bóng đèn đánh số $1..n$, ban đầu đều tắt. Lần lượt $n$ bạn đi qua; bạn thứ $i$ bấm công tắc (tắt thành bật, bật thành tắt) của mọi đèn có số thứ tự chia hết cho $i$. Sau khi cả $n$ bạn đi qua, trong các đèn từ số $a$ tới số $b$ có bao nhiêu đèn đang sáng? ($1 \le a \le b \le n \le 10^{18}$.) Input: $n$, $a$, $b$.
10 2 92📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll isqrt_(ll n){
ll r = sqrtl((long double)n);
while(r * r > n) r--;
while((r + 1) * (r + 1) <= n) r++;
return r;
}
int main(){
ll n, a, b;
cin >> n >> a >> b;
cout << isqrt_(b) - isqrt_(a - 1);
return 0;
}from math import isqrt
n, a, b = map(int, input().split())
print(isqrt(b) - isqrt(a - 1))Cho dãy $n$ số nguyên dương ($1 \le n \le 10^5$, $1 \le a_i \le 10^9$). In ra BCNN của cả dãy, hoặc in -1 nếu BCNN lớn hơn $10^{18}$.
4
4 6 10 1560📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll LIM = 1000000000000000000LL;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n;
cin >> n;
ll l = 1;
bool over = false;
for(int i = 0; i < n; i++){
ll x;
cin >> x;
if(over) continue;
ll t = l / __gcd(l, x);
if(t > LIM / x) over = true;
else l = t * x;
}
if(over) cout << -1; else cout << l;
return 0;
}import sys
from math import gcd
data = sys.stdin.buffer.read().split()
n = int(data[0])
l, LIM = 1, 10 ** 18
for v in data[1:1 + n]:
x = int(v)
l = l // gcd(l, x) * x
if l > LIM:
l = -1
break
print(l)Bạn Tý coi các số $x$, $y$, $z$ là số xui. Một số nguyên dương được gọi là may mắn nếu nó không chia hết cho số xui nào. Đếm số may mắn trong đoạn $[1, n]$. ($1 \le n \le 10^{18}$, $1 \le x, y, z \le 10^{18}$.) Input: $n$, $x$, $y$, $z$.
30 2 3 58📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
ll lcmCap(ll x, ll y){ // BCNN, nhưng nếu > n thì trả về n + 1
if(x > n || y > n) return n + 1;
x /= __gcd(x, y);
if(x > n / y) return n + 1; // x * y > n
return x * y;
}
int main(){
ll x, y, z;
cin >> n >> x >> y >> z;
ll xy = lcmCap(x, y), xz = lcmCap(x, z), yz = lcmCap(y, z), xyz = lcmCap(xy, z);
ll hop = n / x + n / y + n / z - n / xy - n / xz - n / yz + n / xyz;
cout << n - hop;
return 0;
}from math import gcd
def lcm(u, v):
return u // gcd(u, v) * v
n, x, y, z = map(int, input().split())
hop = (n // x + n // y + n // z - n // lcm(x, y) - n // lcm(x, z) - n // lcm(y, z)
+ n // lcm(lcm(x, y), z))
print(n - hop)Số nguyên dương $x$ gọi là dồi dào nếu tổng các ước của nó (kể cả chính nó) lớn hơn $2x$, ví dụ 12 có tổng ước $28 > 24$. Có $Q$ câu hỏi ($Q \le 10^5$), mỗi câu cho $l$, $r$ ($1 \le l \le r \le 10^6$): đếm số dồi dào trong $[l, r]$.
3
1 30
13 20
1 115
2
0📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
s[j] cho mọi $j \le 10^6$ (phần 3), đánh dấu số dồi dào, rồi dựng mảng cộng dồn c[j] = số dồi dào trong $[1, j]$ như bài 13; mỗi câu hỏi trả lời bằng c[r] - c[l-1]. Các số dồi dào không quá 30 là 12, 18, 20, 24, 30, nên đoạn $[13, 20]$ có 2 số. Tổng ước của số tới $10^6$ chưa vượt $5 \cdot 10^6$ nên int là đủ.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
const int MAXV = 1000000;
int s[MAXV + 1], c[MAXV + 1];
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
for(int i = 1; i <= MAXV; i++)
for(int j = i; j <= MAXV; j += i) s[j] += i;
for(int j = 1; j <= MAXV; j++)
c[j] = c[j - 1] + (s[j] > 2 * j ? 1 : 0);
int q;
cin >> q;
while(q--){
int l, r;
cin >> l >> r;
cout << c[r] - c[l - 1] << "\n";
}
return 0;
}import sys
data = sys.stdin.buffer.read().split()
q = int(data[0])
qs = [(int(data[1 + 2 * k]), int(data[2 + 2 * k])) for k in range(q)]
M = max(r for _, r in qs)
s = [0] * (M + 1)
for i in range(1, M + 1):
for j in range(i, M + 1, i):
s[j] += i
c = [0] * (M + 1)
for j in range(1, M + 1):
c[j] = c[j - 1] + (s[j] > 2 * j)
print('\n'.join(str(c[r] - c[l - 1]) for l, r in qs))Cho dãy $n$ số nguyên dương ($2 \le n \le 10^5$, $a_i \le 10^9$). Hãy xoá đúng một phần tử sao cho ƯCLN của $n - 1$ phần tử còn lại lớn nhất. In ra ƯCLN lớn nhất đó.
4
12 15 18 73📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
pre[i] = ƯCLN tiền tố và suf[i] = ƯCLN hậu tố như bảng 5, với pre[0] = suf[n+1] = 0. Bỏ $a_i$ được $\gcd(\text{pre}[i-1], \text{suf}[i+1])$; lấy max theo $i$. Độ phức tạp $O(n \log)$. Mẫu: bỏ số 7 được $\gcd(12, 15, 18) = 3$.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int a[100005], pre[100005], suf[100005];
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n;
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
pre[0] = 0; suf[n + 1] = 0;
for(int i = 1; i <= n; i++) pre[i] = __gcd(pre[i - 1], a[i]);
for(int i = n; i >= 1; i--) suf[i] = __gcd(suf[i + 1], a[i]);
int best = 0;
for(int i = 1; i <= n; i++)
best = max(best, __gcd(pre[i - 1], suf[i + 1]));
cout << best;
return 0;
}import sys
from math import gcd
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = [0] + [int(v) for v in data[1:1 + n]] + [0]
pre = [0] * (n + 2)
suf = [0] * (n + 2)
for i in range(1, n + 1):
pre[i] = gcd(pre[i - 1], a[i])
for i in range(n, 0, -1):
suf[i] = gcd(suf[i + 1], a[i])
print(max(gcd(pre[i - 1], suf[i + 1]) for i in range(1, n + 1)))Cho $n$ số nguyên dương ($1 \le n \le 10^5$, $a_i \le 10^6$). Gọi $P = a_1 \cdot a_2 \cdots a_n$. In số ước của $P$ sau khi chia lấy dư cho $10^9 + 7$.
3
4 6 916📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
spf[x] = ước nguyên tố nhỏ nhất của $x$ (giống sàng Eratosthenes), rồi tách mỗi $a_i$ bằng cách chia liên tục cho spf, cộng số mũ vào e[p]. Đáp án là tích các $(e[p] + 1)$ lấy dư $10^9 + 7$ (phần 3). Mẫu: $P = 4 \cdot 6 \cdot 9 = 216 = 2^3 \cdot 3^3$, số ước $4 \cdot 4 = 16$.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
const int MAXV = 1000000;
const long long MOD = 1000000007;
int spf[MAXV + 1];
long long e[MAXV + 1];
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
for(int i = 2; i <= MAXV; i++)
if(spf[i] == 0) // i nguyên tố
for(int j = i; j <= MAXV; j += i)
if(spf[j] == 0) spf[j] = i;
int n;
cin >> n;
for(int k = 0; k < n; k++){
int x;
cin >> x;
while(x > 1){ // tách x bằng spf: O(log x)
int p = spf[x];
while(x % p == 0){ x /= p; e[p]++; }
}
}
long long ans = 1;
for(int p = 2; p <= MAXV; p++)
if(e[p]) ans = ans * ((e[p] + 1) % MOD) % MOD;
cout << ans;
return 0;
}import sys
from math import isqrt
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = [int(v) for v in data[1:1 + n]]
M = max(a)
MOD = 10 ** 9 + 7
spf = list(range(M + 1)) # spf[x] = ước nguyên tố nhỏ nhất của x
for i in range(isqrt(M), 1, -1): # i giảm dần: số nguyên tố nhỏ ghi đè sau cùng
if all(i % p for p in range(2, isqrt(i) + 1)):
spf[i * i::i] = [i] * len(range(i * i, M + 1, i))
e = {}
for x in a:
while x > 1:
p = spf[x]
while x % p == 0:
x //= p
e[p] = e.get(p, 0) + 1
ans = 1
for v in e.values():
ans = ans * (v + 1) % MOD
print(ans)Cho xâu $s$ gồm toàn chữ số, độ dài không quá $10^5$. Đếm số cặp $(l, r)$ với $l \le r$ sao cho số tạo bởi các chữ số $s_l s_{l+1} \ldots s_r$ chia hết cho 3 (số có thể bắt đầu bằng chữ số 0, ví dụ “03” vẫn tính là số 3).
12366📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
cnt[0..2] = số tiền tố đã gặp theo số dư (ban đầu cnt[0] = 1 cho tiền tố rỗng), cộng cnt[P_r % 3] vào đáp án. Mẫu có 6 đoạn: 3, 6, 12, 36, 123, 1236. Đáp án có thể tới $5 \cdot 10^9$ nên dùng long long.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
string s;
cin >> s;
long long cnt[3] = {1, 0, 0}; // tiền tố rỗng có tổng 0
long long ans = 0;
int p = 0; // tổng chữ số tiền tố, chỉ giữ số dư cho 3
for(char c : s){
p = (p + (c - '0')) % 3;
ans += cnt[p]; // ghép với mọi tiền tố cùng số dư
cnt[p]++;
}
cout << ans;
return 0;
}s = input().strip()
cnt = [1, 0, 0] # tiền tố rỗng có tổng 0
ans = p = 0
for c in s:
p = (p + ord(c) - 48) % 3
ans += cnt[p] # ghép với mọi tiền tố cùng số dư
cnt[p] += 1
print(ans)
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét