Bài 12: Số học cơ bản trong C++ và Python: chia lấy dư, ước số, UCLN – BCNN, số nguyên tố, sàng Eratosthenes
Lời mở đầu
Số học là mảng kiến thức “ăn điểm” dễ nhất trong đề thi, nhưng cũng là nơi nhiều bạn bị TLE nhất vì dùng cách duyệt ngây thơ. Ví dụ kiểm tra $n = 10^{12}$ có phải số nguyên tố không: thử chia cho mọi số từ 2 tới $n - 1$ cần $10^{12}$ phép chia (khoảng 3 tiếng!), trong khi chỉ cần thử tới $\sqrt{n} = 10^6$ là đủ, chưa tới 0,01 giây. Bài này đi qua các thuật toán số học nền tảng, với mỗi thuật toán đều giải thích vì sao nó đúng và vì sao nó nhanh, dựa trên kiến thức độ phức tạp ở bài 9.
Lộ trình bài viết, bấm vào từng phần để nhảy tới:
Phần 1Phép chia lấy dư và modulo
Với số nguyên, a / b cho thương (bỏ phần thập phân) và a % b cho số dư: 17 / 5 = 3, 17 % 5 = 2, vì $17 = 5 \cdot 3 + 2$. Phép % dùng ở khắp nơi: kiểm tra chia hết (a % b == 0), chẵn lẻ (a % 2), lấy chữ số cuối (n % 10), đổi giây sang giờ – phút – giây…
Nhiều đề yêu cầu “in kết quả theo modulo $10^9 + 7$” vì kết quả thật quá lớn (ví dụ $2^{1000}$). Ta không tính kết quả thật rồi mới chia lấy dư (sẽ tràn số), mà lấy dư ngay sau mỗi phép tính nhờ các tính chất:
-7 % 3 == -1 (dấu theo số bị chia), trong Python lại bằng 2. Muốn luôn ra số dư không âm trong C++: ((a % m) + m) % m. 2. Phép trừ: (a - b) % m có thể âm, cũng phải cộng thêm m. 3. Tràn số khi nhân: hai số dưới $10^9 + 7$ nhân nhau có thể tới $10^{18}$, phải dùng long long hoặc 1LL * a * b % m. Không có tính chất tương tự cho phép chia!Ví dụ: n giai thừa theo modulo 10^9 + 7
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
int main(){
int n;
cin >> n;
long long gt = 1; // n! mod 10^9+7
for(int i = 1; i <= n; i++)
gt = gt * i % MOD; // lấy dư sau MỖI phép nhân
cout << gt << "\n";
cout << 17 / 5 << " " << 17 % 5 << " " << -7 % 3 << " " << ((-7 % 3) + 3) % 3;
return 0;
}MOD = 10**9 + 7
n = int(input())
gt = 1
for i in range(1, n + 1):
gt = gt * i % MOD
print(gt)
print(17 // 5, 17 % 5, -7 % 3) # Python: -7 % 3 = 2 (luôn không âm khi m > 0)Phần 2Liệt kê ước số trong O(√n)
$d$ là ước của $n$ nếu n % d == 0. Cách ngây thơ thử mọi $d$ từ 1 tới $n$ mất $O(n)$. Nhận xét then chốt: ước luôn đi theo cặp $d$ và $\frac{n}{d}$, và trong mỗi cặp luôn có một số $\le \sqrt{n}$ (nếu cả hai đều lớn hơn $\sqrt{n}$ thì tích của chúng lớn hơn $n$, vô lý). Vậy chỉ cần thử $d$ từ 1 tới $\sqrt{n}$, mỗi lần tìm được $d$ thì có luôn ước thứ hai là $\frac{n}{d}$. Cẩn thận khi $d = \frac{n}{d}$ (tức $n$ là số chính phương) thì chỉ tính một lần.
Code C++ và Python
#include <bits/stdc++.h>
using namespace std;
int main(){
long long n;
cin >> n;
vector<long long> nho, lon;
for(long long d = 1; d * d <= n; d++){
if(n % d == 0){
nho.push_back(d);
if(d != n / d) lon.push_back(n / d);
}
}
reverse(lon.begin(), lon.end());
for(long long x : nho) cout << x << " ";
for(long long x : lon) cout << x << " ";
return 0;
}n = int(input())
nho, lon = [], []
d = 1
while d * d <= n:
if n % d == 0:
nho.append(d)
if d != n // d:
lon.append(n // d)
d += 1
print(*(nho + lon[::-1]))Phần 3UCLN bằng thuật toán Euclid, BCNN
Ước chung lớn nhất UCLN$(a, b)$ (tiếng Anh: GCD) là số lớn nhất chia hết cả $a$ và $b$. Thuật toán Euclid hơn 2300 tuổi dựa trên một tính chất: UCLN$(a, b)$ = UCLN$(b, a \bmod b)$, và UCLN$(a, 0) = a$. Mỗi bước thay cặp $(a, b)$ bằng $(b, a \% b)$, các số giảm rất nhanh (ít nhất một nửa sau hai bước) nên độ phức tạp chỉ $O(\log \min(a, b))$: với $a, b$ tới $10^{18}$ cũng chỉ vài chục bước.
Bội chung nhỏ nhất BCNN$(a, b) = \dfrac{a \cdot b}{\text{UCLN}(a, b)}$. Mẹo chống tràn số: tính a / ucln * b (chia trước, nhân sau).
Code C++ và Python
#include <bits/stdc++.h>
using namespace std;
int main(){
long long a, b;
cin >> a >> b;
long long x = a, y = b;
while(y != 0){
long long r = x % y;
x = y;
y = r;
}
long long ucln = x;
long long bcnn = a / ucln * b;
cout << ucln << " " << bcnn;
return 0;
}import math
a, b = map(int, input().split())
x, y = a, b
while y != 0:
x, y = y, x % y
ucln = x # hoặc math.gcd(a, b)
print(ucln, a // ucln * b) # Python 3.9+: math.lcm(a, b)gcd(a, b) và lcm(a, b) trong <numeric>; trình biên dịch GCC cũ hơn có __gcd(a, b). Python có math.gcd (và math.lcm từ bản 3.9). UCLN của cả dãy: g = 0; rồi g = gcd(g, a[i]) với mọi $i$. Phân số $\frac{a}{b}$ tối giản khi chia cả tử và mẫu cho UCLN$(a, b)$.Mô phỏng trực quan. Thuật toán Euclid chỉ vài dòng nhưng nhiều bạn chưa thấy vì sao nó dừng nhanh đến thế. Em nhập hai số rồi bấm Tiếp: mỗi vòng là một phép chia a = q × b + r, hai thanh màu cho thấy các số co lại rất nhanh. Thử cả a < b và hai số Fibonacci liền nhau như 89 và 55 nhé.
Phần 4Số nguyên tố và sàng Eratosthenes
Số nguyên tố là số tự nhiên lớn hơn 1, chỉ có đúng hai ước là 1 và chính nó: 2, 3, 5, 7, 11, 13… (1 không phải số nguyên tố, 2 là số nguyên tố chẵn duy nhất). Theo nhận xét ở phần 2, nếu $n$ có một ước nằm giữa 2 và $n - 1$ thì nó phải có một ước $\le \sqrt{n}$. Vậy để kiểm tra chỉ cần thử chia cho các số từ 2 tới $\sqrt{n}$, độ phức tạp $O(\sqrt{n})$.
Code C++ và Python
#include <bits/stdc++.h>
using namespace std;
bool laNguyenTo(long long n){
if(n < 2) return false;
for(long long i = 2; i * i <= n; i++)
if(n % i == 0) return false;
return true;
}
int main(){
long long n;
cin >> n;
cout << (laNguyenTo(n) ? "YES" : "NO");
return 0;
}def la_nguyen_to(n):
if n < 2:
return False
i = 2
while i * i <= n:
if n % i == 0:
return False
i += 1
return True
print("YES" if la_nguyen_to(int(input())) else "NO")Sàng Eratosthenes. Khi cần biết tất cả số nguyên tố từ 1 tới $n$ (ví dụ $n = 10^7$), kiểm tra từng số mất $O(n\sqrt{n})$, quá chậm. Nhà toán học Hy Lạp Eratosthenes nghĩ ra cách “sàng”: viết các số từ 2 tới $n$; số nhỏ nhất chưa bị gạch (2) là nguyên tố, gạch mọi bội của nó; số nhỏ nhất tiếp theo chưa bị gạch (3) là nguyên tố, gạch mọi bội của nó… Hai mẹo tăng tốc: chỉ cần sàng với các số nguyên tố $p \le \sqrt{n}$, và bắt đầu gạch từ $p^2$ (các bội nhỏ hơn đã bị gạch bởi số nguyên tố nhỏ hơn). Độ phức tạp chỉ $O(n \log \log n)$, gần như $O(n)$.
Code C++ và Python
#include <bits/stdc++.h>
using namespace std;
bool nt[10000005];
int main(){
int n;
cin >> n;
for(int i = 2; i <= n; i++) nt[i] = true;
for(int p = 2; p * p <= n; p++){
if(nt[p]){
for(int j = p * p; j <= n; j += p)
nt[j] = false;
}
}
for(int i = 2; i <= n; i++)
if(nt[i]) cout << i << " ";
return 0;
}n = int(input())
nt = [True] * (n + 1)
nt[0] = nt[1] = False
p = 2
while p * p <= n:
if nt[p]:
for j in range(p * p, n + 1, p):
nt[j] = False
p += 1
print(*[i for i in range(n + 1) if nt[i]])Xem sàng chạy trên bảng số lớn hơn: chọn $n$ (tới 120) rồi bấm Tự chạy. Mỗi màu ứng với các bội bị gạch bởi một số nguyên tố; để ý các số nguyên tố lớn hơn $\sqrt{n}$ không cần sàng mà vẫn được giữ lại.
Phần 5Phân tích thừa số nguyên tố
Mọi số nguyên $n \ge 2$ đều viết được duy nhất thành tích các số nguyên tố, ví dụ $360 = 2^3 \cdot 3^2 \cdot 5$. Cách làm: thử chia $n$ cho $i = 2, 3, 4, \dots$; chừng nào còn chia hết cho $i$ thì chia và ghi nhận $i$. Không cần kiểm tra $i$ có nguyên tố không: khi tới $i = 4$ thì mọi thừa số 2 đã bị chia hết rồi, nên 4 không thể chia hết $n$ nữa. Chỉ cần thử tới $\sqrt{n}$; nếu cuối cùng $n$ còn lớn hơn 1 thì phần còn lại chính là một số nguyên tố (lớn hơn $\sqrt{n}$ ban đầu).
Code C++ và Python
#include <bits/stdc++.h>
using namespace std;
int main(){
long long n;
cin >> n;
for(long long i = 2; i * i <= n; i++){
int mu = 0;
while(n % i == 0){
n /= i;
mu++;
}
if(mu > 0) cout << i << "^" << mu << " ";
}
if(n > 1) cout << n << "^1";
return 0;
}n = int(input())
kq = []
i = 2
while i * i <= n:
mu = 0
while n % i == 0:
n //= i
mu += 1
if mu > 0:
kq.append(f"{i}^{mu}")
i += 1
if n > 1:
kq.append(f"{n}^1")
print(' '.join(kq))Mô phỏng trực quan. Đọc code phân tích thừa số, nhiều bạn thắc mắc: i chạy cả 4, 6, 8 thì có ghi nhầm hợp số không? Em bấm Tiếp để xem n bị chia nhỏ dần, i tăng dần và vì sao chỉ cần thử tới khi i × i > n. Thử thêm một số nguyên tố lớn như 999999937 để thấy bước cuối.
Bài tậpLuyện số học
Cho $n$ ($1 \le n \le 10^{12}$). Tính tổng tất cả các ước nguyên dương của $n$.
1228💡 Gợi ý
long long.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
long long n, s = 0;
cin >> n;
for(long long d = 1; d * d <= n; d++){
if(n % d == 0){
s += d;
if(d != n / d) s += n / d;
}
}
cout << s;
return 0;
}n = int(input())
s, d = 0, 1
while d * d <= n:
if n % d == 0:
s += d
if d != n // d:
s += n // d
d += 1
print(s)Cho hai số nguyên dương $a, b \le 10^9$. In UCLN và BCNN của chúng.
12 186 36💡 Gợi ý
a / g * b với long long.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
long long ucln(long long a, long long b){
while(b != 0){ long long r = a % b; a = b; b = r; }
return a;
}
int main(){
long long a, b;
cin >> a >> b;
long long g = ucln(a, b);
cout << g << " " << a / g * b;
return 0;
}import math
a, b = map(int, input().split())
g = math.gcd(a, b)
print(g, a // g * b)Cho phân số $\frac{a}{b}$ với $a, b$ nguyên dương ($\le 10^{18}$). In tử và mẫu của phân số tối giản.
84 367 3💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
long long a, b;
cin >> a >> b;
long long x = a, y = b;
while(y){ long long r = x % y; x = y; y = r; }
cout << a / x << " " << b / x;
return 0;
}import math
a, b = map(int, input().split())
g = math.gcd(a, b)
print(a // g, b // g)Cho $t$ số nguyên $n_i$ ($t \le 100$, $n_i \le 10^{12}$). Với mỗi số in YES nếu là số nguyên tố, ngược lại in NO.
4
2 15 97 1YES
NO
YES
NO💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
bool nt(long long n){
if(n < 2) return false;
for(long long i = 2; i * i <= n; i++) if(n % i == 0) return false;
return true;
}
int main(){
int t;
cin >> t;
while(t--){
long long n; cin >> n;
cout << (nt(n) ? "YES" : "NO") << "\n";
}
return 0;
}def nt(n):
if n < 2:
return False
i = 2
while i * i <= n:
if n % i == 0:
return False
i += 1
return True
t = int(input())
a = list(map(int, input().split()))
print('\n'.join("YES" if nt(x) else "NO" for x in a))Cho $n$ ($n \le 10^7$). Đếm số các số nguyên tố không vượt quá $n$.
10025💡 Gợi ý
bool $10^7$ phần tử (khoảng 10 MB), rồi đếm số ô còn true. Kiểm tra từng số bằng $O(\sqrt{n})$ sẽ mất khoảng $10^{10}$ phép tính → TLE.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
bool hop[10000005]; // hop[i] = true nếu i là hợp số
int main(){
int n;
cin >> n;
int dem = 0;
for(int i = 2; i <= n; i++){
if(!hop[i]){
dem++;
for(long long j = 1LL * i * i; j <= n; j += i) hop[j] = true;
}
}
cout << dem;
return 0;
}n = int(input())
nt = bytearray([1]) * (n + 1)
nt[0:2] = b'\x00\x00'
p = 2
while p * p <= n:
if nt[p]:
nt[p * p::p] = bytearray(len(range(p * p, n + 1, p)))
p += 1
print(sum(nt))Cho $n$ ($2 \le n \le 10^{12}$). In phân tích thừa số nguyên tố dạng p1^e1 * p2^e2 * ... theo thứ tự tăng dần, số mũ bằng 1 thì không in ^1.
3602^3 * 3^2 * 5💡 Gợi ý
" * ".Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
long long n;
cin >> n;
vector<string> kq;
for(long long i = 2; i * i <= n; i++){
int mu = 0;
while(n % i == 0){ n /= i; mu++; }
if(mu == 1) kq.push_back(to_string(i));
else if(mu > 1) kq.push_back(to_string(i) + "^" + to_string(mu));
}
if(n > 1) kq.push_back(to_string(n));
for(int k = 0; k < (int)kq.size(); k++){
if(k) cout << " * ";
cout << kq[k];
}
return 0;
}n = int(input())
kq, i = [], 2
while i * i <= n:
mu = 0
while n % i == 0:
n //= i
mu += 1
if mu:
kq.append(str(i) if mu == 1 else f"{i}^{mu}")
i += 1
if n > 1:
kq.append(str(n))
print(' * '.join(kq))Số hoàn hảo là số bằng tổng các ước nhỏ hơn nó, ví dụ $6 = 1 + 2 + 3$. Cho $n \le 10^6$, in tất cả số hoàn hảo không vượt quá $n$.
100006 28 496 8128💡 Gợi ý
s[2d], s[3d], s[4d], … (các bội của $d$ lớn hơn $d$). Số phép tính là $\frac{n}{1} + \frac{n}{2} + \dots \approx n \ln n$, tức $O(n \log n)$.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
long long s[1000005];
int main(){
int n;
cin >> n;
for(int d = 1; d <= n; d++)
for(int j = 2 * d; j <= n; j += d) s[j] += d;
for(int i = 2; i <= n; i++)
if(s[i] == i) cout << i << " ";
return 0;
}n = int(input())
s = [0] * (n + 1)
for d in range(1, n // 2 + 1):
for j in range(2 * d, n + 1, d):
s[j] += d
print(*[i for i in range(2, n + 1) if s[i] == i])Cho $a, b, m$ ($a, m \le 10^9$, $b \le 10^{18}$, $m \ge 2$). Tính $a^b \bmod m$.
2 10 100024💡 Gợi ý
pow(a, b, m).Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
long long a, b, m;
cin >> a >> b >> m;
long long kq = 1 % m;
a %= m;
while(b > 0){
if(b % 2 == 1) kq = kq * a % m;
a = a * a % m;
b /= 2;
}
cout << kq;
return 0;
}a, b, m = map(int, input().split())
print(pow(a, b, m))
- 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