Chuyên đề 3: Số nguyên lớn (Big Int) trong C++ và Python: cộng, trừ, nhân, chia số lớn bằng xâu
Lời mở đầu
Ở bài 2 em đã biết int chỉ chứa tới khoảng $2{,}1 \cdot 10^9$, còn long long chứa tới $9\,223\,372\,036\,854\,775\,807 \approx 9{,}2 \cdot 10^{18}$, tức chỉ khoảng 19 chữ số. Vượt quá giới hạn đó máy tính không báo lỗi gì cả, nó lặng lẽ cho ra một số sai (thường là số âm). Hiện tượng này gọi là tràn số, và ở bài 9 mình đã dặn: tràn số là một trong những lý do mất điểm “oan” nhiều nhất khi chấm bài. Vậy nếu đề bảo tính $25! = 15\,511\,210\,043\,330\,985\,984\,000\,000$ (26 chữ số), hay cộng hai số có tới 1000 chữ số thì sao?
Câu trả lời: cất số vào một xâu (bài 8), mỗi ký tự là một chữ số, rồi tự viết các phép cộng, trừ, nhân, chia từng chữ số một, giống hệt cách em đặt tính trên giấy. Kỹ thuật này gọi là số lớn (big int). Python có sẵn số nguyên không giới hạn nên làm rất nhàn, nhưng đi thi HSG bằng C++ thì em phải tự cài. Tin vui là cả bốn phép tính đều ngắn, chỉ 10–15 dòng mỗi phép, và em sẽ thấy chúng quen thuộc đến bất ngờ.
Lộ trình bài viết, bấm vào từng phần để nhảy tới:
Phần 1Biểu diễn và so sánh hai số lớn
Hãy thử chạy đoạn code nhỏ này trong đầu: long long x = 9000000000000000000; x = x * 2;. Kết quả đúng là $1{,}8 \cdot 10^{19}$, nhưng nó vượt giới hạn $9{,}2 \cdot 10^{18}$ nên máy in ra -446744073709551616. Đề bài số lớn thường cho số có hàng trăm, hàng nghìn chữ số, nên không kiểu số nguyên nào của C++ chứa nổi. (double chứa được số rất lớn nhưng chỉ giữ khoảng 15–16 chữ số đầu, phần sau bị làm tròn, xem lại chuyên đề 2.)
Cách 1: lưu bằng xâu. Đọc thẳng số vào string s. Ký tự s[i] là chữ số dạng ký tự, muốn lấy giá trị thì trừ đi '0': s[i] - '0'. Ngược lại, muốn đổi chữ số x (0…9) thành ký tự thì viết char(x + '0'). Cách này đọc, in rất tiện, nhưng có một điều bất tiện: s[0] là chữ số hàng cao nhất, còn hàng đơn vị lại nằm ở cuối xâu.
Cách 2: lưu mảng chữ số đảo ngược. Dùng vector<int> d với d[0] là hàng đơn vị, d[1] hàng chục, d[i] là chữ số nhân với $10^i$. Cách này đẹp khi tính toán: chữ số ở “hàng $10^i$” nằm đúng ở ô $i$, và khi kết quả dài thêm thì chỉ cần push_back vào cuối.
Hình 1. Hai cách lưu số 90817. Xâu s giữ đúng thứ tự đọc (s[0] = 9 là hàng chục nghìn), mảng d đảo ngược lại (d[0] = 7 là hàng đơn vị, d[i] ứng với $10^i$).
So sánh hai số lớn. Có thể so sánh hai xâu bằng < được không? Thử "9" < "10": kết quả là sai, vì xâu so sánh theo thứ tự từ điển, thấy ký tự đầu '9' > '1' là kết luận luôn. Với số thì phải làm hai bước:
- Bỏ các chữ số 0 thừa ở đầu (
"007"thành"7","000"thành"0"). - Số nào nhiều chữ số hơn thì lớn hơn. Nếu cùng độ dài thì mới so sánh từ điển, vì khi đó chữ số đầu tiên khác nhau quyết định tất cả.
| a | b | So độ dài | So từ điển | Kết luận |
|---|---|---|---|---|
| 9 | 10 | 1 < 2 | (không cần) | 9 < 10 |
| 54321 | 54312 | 5 = 5 | khác nhau ở vị trí 3: 2 > 1 | 54321 > 54312 |
| 00123 | 99 | sau khi bỏ số 0: 3 > 2 | (không cần) | 123 > 99 |
| 0000 | 0 | sau khi bỏ số 0: 1 = 1 | "0" = "0" | bằng nhau |
Bảng 1. So sánh hai số lớn: luôn so độ dài trước, cùng độ dài mới so từ điển.
Xem code C++ / Python: so sánh hai số lớn (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
// bỏ các chữ số 0 thừa ở đầu, "000" -> "0"
string chuanHoa(string s){
int p = 0;
while(p + 1 < (int)s.size() && s[p] == '0') p++;
return s.substr(p);
}
// trả về -1 nếu a < b, 0 nếu a = b, 1 nếu a > b
int soSanh(string a, string b){
a = chuanHoa(a); b = chuanHoa(b);
if(a.size() != b.size()) // số nào nhiều chữ số hơn thì lớn hơn
return a.size() < b.size() ? -1 : 1;
if(a == b) return 0;
return a < b ? -1 : 1; // cùng độ dài: so sánh từ điển
}
int main(){
string a, b;
cin >> a >> b;
int c = soSanh(a, b);
if(c < 0) cout << "<";
else if(c > 0) cout << ">";
else cout << "=";
return 0;
}def chuan_hoa(s): # bỏ các chữ số 0 thừa ở đầu
s = s.lstrip('0')
return s if s else '0'
def so_sanh(a, b): # -1, 0 hoặc 1
a, b = chuan_hoa(a), chuan_hoa(b)
if len(a) != len(b): # nhiều chữ số hơn thì lớn hơn
return -1 if len(a) < len(b) else 1
if a == b:
return 0
return -1 if a < b else 1 # cùng độ dài: so sánh từ điển
a, b = input().split()
print({-1: '<', 0: '=', 1: '>'}[so_sanh(a, b)])chữ số viết xuống = s % 10, nhớ sang cột trái = s / 10.Phần 2Cộng hai số lớn
Em nhớ lại phép đặt tính $9876 + 789$ hồi lớp 2–3: viết hai số thẳng cột theo hàng đơn vị, cộng từ phải sang trái, cột nào được từ 10 trở lên thì “viết hàng đơn vị, nhớ 1 sang cột bên trái”. Máy tính làm y hệt như vậy:
| Cột | Chữ số a | Chữ số b | Nhớ cũ | s = tổng | Viết (s % 10) | Nhớ mới (s / 10) |
|---|---|---|---|---|---|---|
| đơn vị | 6 | 9 | 0 | 15 | 5 | 1 |
| chục | 7 | 8 | 1 | 16 | 6 | 1 |
| trăm | 8 | 7 | 1 | 16 | 6 | 1 |
| nghìn | 9 | (hết) 0 | 1 | 10 | 0 | 1 |
| chục nghìn | (hết) 0 | (hết) 0 | 1 | 1 | 1 | 0 |
Bảng 2. Cộng $9876 + 789$ từng cột. Đọc cột “Viết” từ dưới lên: 10665. Để ý hàng cuối: hai số đã hết chữ số nhưng vẫn còn nhớ 1, nên kết quả dài thêm một chữ số.
Ba điểm em cần để ý khi chuyển sang code:
- Dùng hai chỉ số
i,jbắt đầu từ cuối hai xâu và lùi dần. Số nào hết chữ số trước thì coi như cộng thêm 0. - Vòng lặp chạy khi còn chữ số hoặc còn nhớ:
while(i >= 0 || j >= 0 || nho > 0). Thiếu điều kiệnnho > 0thì $999 + 1$ ra000thay vì1000. - Ta viết kết quả từ hàng đơn vị nên xâu
resbị ngược, cuối cùng phảireverselại.
Em bấm Tiếp để xem từng cột được cộng thế nào, rồi thử tự nhập hai số khác (chẳng hạn 999999 và 1 để thấy số nhớ “chạy” suốt từ phải sang trái):
Xem code C++ / Python: cộng hai số lớn (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
string cong(string a, string b){
string res = "";
int i = a.size() - 1, j = b.size() - 1, nho = 0;
while(i >= 0 || j >= 0 || nho > 0){ // còn chữ số hoặc còn nhớ
int s = nho;
if(i >= 0) s += a[i--] - '0'; // chữ số của a ở cột này
if(j >= 0) s += b[j--] - '0'; // chữ số của b ở cột này
res += char(s % 10 + '0'); // viết hàng đơn vị của s
nho = s / 10; // nhớ sang cột bên trái
}
reverse(res.begin(), res.end()); // ta viết từ hàng đơn vị nên phải đảo lại
return res;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
string a, b;
cin >> a >> b;
cout << cong(a, b);
return 0;
}import sys
def cong(a, b):
res = []
i, j, nho = len(a) - 1, len(b) - 1, 0
while i >= 0 or j >= 0 or nho > 0: # còn chữ số hoặc còn nhớ
s = nho
if i >= 0:
s += ord(a[i]) - 48; i -= 1 # ord('0') = 48
if j >= 0:
s += ord(b[j]) - 48; j -= 1
res.append(chr(s % 10 + 48)) # viết hàng đơn vị của s
nho = s // 10 # nhớ sang cột bên trái
return ''.join(reversed(res))
a, b = sys.stdin.read().split()
print(cong(a, b))Bây giờ em chạy tay từng dòng code C++ (cùng thuật toán, viết gọn trong main). Hãy để ý biến nho và xâu res đang dài ra theo thứ tự ngược:
'0': cộng thẳng hai ký tự '7' + '8' được 55 + 56 = 111 chứ không phải 15.2. Quên điều kiện
nho > 0 trong vòng lặp, làm mất chữ số 1 ở đầu.3. Quên
reverse ở cuối. Với ví dụ trên em sẽ in ra 56601. Thử ngay với $999 + 1$: in ra 0001 là biết quên đảo.4. Viết
res = char(...) + res (chèn vào đầu xâu) thay vì res += ... rồi đảo: đúng nhưng mỗi lần chèn phải dời cả xâu, số có $10^5$ chữ số sẽ chạy rất chậm ($O(n^2)$).Phần 3Trừ hai số lớn
Phép trừ cũng đi từ phải sang trái, chỉ khác là thay “nhớ” bằng “mượn”. Ta tạm giả sử $a \ge b$ (lát nữa sẽ xử lý trường hợp ngược lại). Ở mỗi cột:
- Tính
s = chữ số a − chữ số b − mượn(số b hết chữ số thì coi như 0). - Nếu
s < 0: không đủ trừ, ta mượn 1 chục từ cột bên trái:s += 10,muon = 1. Ngược lạimuon = 0. - Viết
sxuống. Vòng lặp chạy theo số a (số dài hơn), vì $a \ge b$ nên cuối cùng không bao giờ còn mượn.
| Cột | Chữ số a | Chữ số b | Mượn cũ | s = a − b − mượn | Mượn 1 chục? | Viết |
|---|---|---|---|---|---|---|
| đơn vị | 0 | 7 | 0 | −7 | có → s = 3 | 3 |
| chục | 0 | (hết) 0 | 1 | −1 | có → s = 9 | 9 |
| trăm | 0 | (hết) 0 | 1 | −1 | có → s = 9 | 9 |
| nghìn | 1 | (hết) 0 | 1 | 0 | không | 0 |
Bảng 3. Tính $1000 - 7$. Đọc cột “Viết” từ dưới lên được 0993: có một số 0 thừa ở đầu, bỏ đi còn 993.
Bảng 3 cho thấy hai việc phải làm thêm so với phép cộng:
- Bỏ số 0 ở đầu kết quả. Hiệu có thể ngắn hơn rất nhiều so với $a$, ví dụ $1000 - 999 = 0001 \to 1$, hay $5 - 5 = 0$. Vì
resđang bị ngược nên các số 0 “ở đầu” lại nằm ở cuốires: cứpop_backkhi nó còn dài hơn 1 và chữ số cuối là 0. Nhớ giữ lại ít nhất một chữ số để $5 - 5$ in ra0chứ không phải xâu rỗng. - Khi $a < b$, kết quả âm. Dùng hàm so sánh ở phần 1, rồi tính $b - a$ và in thêm dấu trừ phía trước: $a - b = -(b - a)$. Ví dụ $100 - 1000 = -(1000 - 100) = -900$.
Xem code C++ / Python: trừ hai số lớn (kể cả kết quả âm) (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
string chuanHoa(string s){
int p = 0;
while(p + 1 < (int)s.size() && s[p] == '0') p++;
return s.substr(p);
}
int soSanh(string a, string b){
a = chuanHoa(a); b = chuanHoa(b);
if(a.size() != b.size()) return a.size() < b.size() ? -1 : 1;
if(a == b) return 0;
return a < b ? -1 : 1;
}
string tru(string a, string b){ // yêu cầu a >= b
string res = "";
int i = a.size() - 1, j = b.size() - 1, muon = 0;
while(i >= 0){
int s = (a[i--] - '0') - muon;
if(j >= 0) s -= b[j--] - '0';
if(s < 0){ s += 10; muon = 1; } // không đủ trừ: mượn 1 chục
else muon = 0;
res += char(s + '0');
}
while(res.size() > 1 && res.back() == '0') // bỏ số 0 ở đầu (đang nằm ở cuối res)
res.pop_back();
reverse(res.begin(), res.end());
return res;
}
int main(){
string a, b;
cin >> a >> b;
a = chuanHoa(a); b = chuanHoa(b);
if(soSanh(a, b) >= 0) cout << tru(a, b);
else cout << "-" << tru(b, a); // a < b: a - b = -(b - a)
return 0;
}def chuan_hoa(s):
s = s.lstrip('0')
return s if s else '0'
def nho_hon(a, b): # a < b ? (đã chuẩn hoá)
return (len(a), a) < (len(b), b)
def tru(a, b): # yêu cầu a >= b
res = []
i, j, muon = len(a) - 1, len(b) - 1, 0
while i >= 0:
s = int(a[i]) - muon; i -= 1
if j >= 0:
s -= int(b[j]); j -= 1
if s < 0: # không đủ trừ: mượn 1 chục
s += 10; muon = 1
else:
muon = 0
res.append(str(s))
while len(res) > 1 and res[-1] == '0': # bỏ số 0 ở đầu
res.pop()
return ''.join(reversed(res))
a, b = map(chuan_hoa, input().split())
print('-' + tru(b, a) if nho_hon(a, b) else tru(a, b))-123), em tách dấu ra riêng rồi quy về phép cộng hoặc trừ hai số không âm: $(-a) + b = b - a$, $(-a) + (-b) = -(a + b)$, $a - (-b) = a + b$… Chỉ cần hai hàm cong, tru và hàm so sánh là đủ mọi trường hợp.Phần 4Nhân số lớn
a) Nhân số lớn với số nhỏ. Đây là phép nhân hay gặp nhất (tính giai thừa, lũy thừa, đổi hệ cơ số…). Số $a$ rất dài, còn $k$ vừa với long long, chẳng hạn $k \le 10^9$. Ta vẫn đi từ phải sang trái, nhưng ở mỗi cột nhân cả số $k$ với một chữ số: s = chữ số × k + nhớ, viết s % 10, nhớ s / 10.
| Cột | Chữ số a | s = chữ số × 25 + nhớ | Viết | Nhớ |
|---|---|---|---|---|
| đơn vị | 7 | 7 × 25 + 0 = 175 | 5 | 17 |
| chục | 4 | 4 × 25 + 17 = 117 | 7 | 11 |
| trăm | 3 | 3 × 25 + 11 = 86 | 6 | 8 |
| (hết chữ số) | viết nốt nhớ 8 | 8 | 0 |
Bảng 4. Tính $347 \times 25$: đọc cột “Viết” từ dưới lên được 8675. Số nhớ ở đây lên tới 17, không còn chỉ là 0 hay 1 như phép cộng.
Hai chỗ khác phép cộng: số nhớ có thể lớn hơn 9 (nên hết chữ số rồi phải dùng vòng while viết nốt từng chữ số của nhớ), và s có thể tới $9 \cdot 10^9 + \text{nhớ}$ nên phải dùng long long. Nhân với $k = 0$ thì trả về "0" luôn để khỏi in ra một dãy số 0.
Xem code C++ / Python: nhân số lớn với số nhỏ (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
string nhanNho(string a, long long k){ // a là số lớn, 0 <= k <= 10^9
if(k == 0) return "0";
string res = "";
long long nho = 0;
for(int i = a.size() - 1; i >= 0; i--){
long long s = (a[i] - '0') * k + nho; // cả chữ số nhân với k, cộng nhớ
res += char(s % 10 + '0');
nho = s / 10; // nhớ có thể lớn hơn 9!
}
while(nho > 0){ // viết nốt phần nhớ còn lại
res += char(nho % 10 + '0');
nho /= 10;
}
reverse(res.begin(), res.end());
return res;
}
int main(){
string a; long long k;
cin >> a >> k;
cout << nhanNho(a, k);
return 0;
}def nhan_nho(a, k): # a là xâu số lớn, k là số nhỏ
if k == 0:
return '0'
res, nho = [], 0
for ch in reversed(a):
s = int(ch) * k + nho # cả chữ số nhân với k, cộng nhớ
res.append(str(s % 10))
nho = s // 10 # nhớ có thể lớn hơn 9!
while nho > 0: # viết nốt phần nhớ còn lại
res.append(str(nho % 10))
nho //= 10
return ''.join(reversed(res))
a, k = input().split()
print(nhan_nho(a, int(k)))b) Nhân hai số lớn. Khi cả hai số đều dài, ta quay về phép đặt tính nhân nhiều chữ số: nhân $a$ với từng chữ số của $b$, mỗi hàng viết lùi sang trái một ô, rồi cộng tất cả lại. Có một mẹo giúp code ngắn hẳn: đánh số chữ số từ phải sang, chữ số $a_i$ mang giá trị $a_i \cdot 10^i$, chữ số $b_j$ mang giá trị $b_j \cdot 10^j$, nên tích của chúng là $a_i b_j \cdot 10^{i+j}$, tức thuộc về hàng $i + j$. Vậy:
- Tạo mảng
resgồm $n + m$ ô toàn 0 (tích của số $n$ chữ số và số $m$ chữ số có không quá $n + m$ chữ số). - Với mọi cặp $(i, j)$:
res[i + j] += a[i] * b[j]. Chưa cần quan tâm nhớ, cứ cộng dồn. - Cuối cùng xử lý nhớ một lượt từ ô 0 lên:
res[k + 1] += res[k] / 10; res[k] %= 10;, rồi bỏ số 0 ở đầu.
| Ô (hàng) | Các tích cộng dồn vào | res trước khi xử lý nhớ | Xử lý nhớ | Chữ số |
|---|---|---|---|---|
| 0 (đơn vị) | 7·8 | 56 | 56 → viết 6, nhớ 5 | 6 |
| 1 (chục) | 4·8 + 7·6 | 32 + 42 = 74 | 74 + 5 = 79 → viết 9, nhớ 7 | 9 |
| 2 (trăm) | 3·8 + 4·6 | 24 + 24 = 48 | 48 + 7 = 55 → viết 5, nhớ 5 | 5 |
| 3 (nghìn) | 3·6 | 18 | 18 + 5 = 23 → viết 3, nhớ 2 | 3 |
| 4 (chục nghìn) | (không có) | 0 | 0 + 2 = 2 | 2 |
Bảng 5. Tính $347 \times 68$ ($a_0 = 7, a_1 = 4, a_2 = 3$; $b_0 = 8, b_1 = 6$). Đọc cột “Chữ số” từ dưới lên: 23596.
Mô phỏng dưới đây vẽ đúng bảng đặt tính: mỗi hàng giữa là một chữ số của $b$ nhân với $a$, các tích rơi vào ô res[i + j] thẳng cột. Em xem cả bước xử lý nhớ ở cuối nhé:
Xem code C++ / Python: nhân hai số lớn trong $O(n \cdot m)$ (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
string nhan(string a, string b){
int n = a.size(), m = b.size();
vector<long long> res(n + m, 0);
for(int i = 0; i < n; i++) // a[n-1-i] là chữ số hàng 10^i của a
for(int j = 0; j < m; j++) // b[m-1-j] là chữ số hàng 10^j của b
res[i + j] += (a[n - 1 - i] - '0') * (b[m - 1 - j] - '0');
for(int k = 0; k + 1 < n + m; k++){ // xử lý nhớ một lượt từ hàng đơn vị
res[k + 1] += res[k] / 10;
res[k] %= 10;
}
int k = n + m - 1;
while(k > 0 && res[k] == 0) k--; // bỏ số 0 ở đầu
string s = "";
for(; k >= 0; k--) s += char(res[k] + '0');
return s;
}
int main(){
string a, b;
cin >> a >> b;
cout << nhan(a, b);
return 0;
}def nhan(a, b):
n, m = len(a), len(b)
A = [int(c) for c in reversed(a)] # A[i]: chữ số hàng 10^i
B = [int(c) for c in reversed(b)]
res = [0] * (n + m)
for i in range(n):
for j in range(m):
res[i + j] += A[i] * B[j] # cộng dồn vào ô i + j
for k in range(n + m - 1): # xử lý nhớ
res[k + 1] += res[k] // 10
res[k] %= 10
k = n + m - 1
while k > 0 and res[k] == 0: # bỏ số 0 ở đầu
k -= 1
return ''.join(str(res[t]) for t in range(k, -1, -1))
a, b = input().split()
print(nhan(a, b))res[i + j] nhận tối đa $\min(n, m)$ tích, nên với hai số 10000 chữ số, một ô có thể tới $81 \cdot 10^4 \approx 8 \cdot 10^5$, int vẫn chứa được. Nhưng nếu sau này em cải tiến lưu mỗi ô 4 hay 9 chữ số cho nhanh hơn thì tích mỗi cặp đã lên tới $10^8$ hay $10^{18}$, nên quen tay dùng long long cho an toàn. Độ phức tạp $O(n \cdot m)$: hai số 2000 chữ số mất $4 \cdot 10^6$ phép nhân, rất nhanh.Phần 5Chia số lớn cho số nhỏ và ứng dụng
Phép chia là phép duy nhất đi từ trái sang phải, đúng như đặt tính chia ở lớp 3–4: hạ từng chữ số xuống, ghép vào sau phần dư cũ, chia lấy một chữ số của thương, phần dư mới lại được mang sang bước sau. Viết bằng công thức, với phần dư r (ban đầu 0) và chữ số tiếp theo c:
r = r * 10 + c; // hạ chữ số c xuống
thương += r / k; // một chữ số của thương
r = r % k; // phần dư mang sangVì luôn có $r < k$ trước khi hạ chữ số, nên $r \cdot 10 + c < 10k$ và r / k luôn là đúng một chữ số (0…9). Với $k \le 10^9$ thì $r \cdot 10 + c < 10^{10}$, phải dùng long long.
| Chữ số hạ xuống | r = r·10 + c | Chữ số thương r / 7 | Dư r % 7 |
|---|---|---|---|
| 1 | 0·10 + 1 = 1 | 0 | 1 |
| 2 | 1·10 + 2 = 12 | 1 | 5 |
| 3 | 5·10 + 3 = 53 | 7 | 4 |
| 4 | 4·10 + 4 = 44 | 6 | 2 |
Bảng 6. Tính $1234 : 7$. Cột thương đọc từ trên xuống là 0176, bỏ số 0 ở đầu được 176, dư 2. Kiểm tra: $176 \cdot 7 + 2 = 1234$.
Xem code C++ / Python: chia số lớn cho số nhỏ (thương và số dư) (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
// trả về thương a / k, phần dư cất vào r (1 <= k <= 10^9)
string chiaNho(string a, long long k, long long &r){
string q = "";
r = 0;
for(int i = 0; i < (int)a.size(); i++){ // từ TRÁI sang phải
r = r * 10 + (a[i] - '0'); // hạ chữ số tiếp theo xuống
q += char(r / k + '0'); // r < 10k nên r / k luôn là 1 chữ số
r = r % k; // phần dư mang sang bước sau
}
int p = 0;
while(p + 1 < (int)q.size() && q[p] == '0') p++;
return q.substr(p); // bỏ số 0 ở đầu thương
}
int main(){
string a; long long k, r;
cin >> a >> k;
string q = chiaNho(a, k, r);
cout << q << " " << r;
return 0;
}def chia_nho(a, k): # trả về (thương, dư)
q, r = [], 0
for ch in a: # từ TRÁI sang phải
r = r * 10 + int(ch) # hạ chữ số tiếp theo xuống
q.append(str(r // k)) # r < 10k nên luôn là 1 chữ số
r %= k # phần dư mang sang bước sau
q = ''.join(q).lstrip('0') or '0'
return q, r
a, k = input().split()
print(*chia_nho(a, int(k)))r = (r * 10 + c) % k. Đây chính là tính chất đồng dư: $(x \cdot 10 + c) \bmod k = ((x \bmod k) \cdot 10 + c) \bmod k$, nên ta không bao giờ phải lưu cả số $a$. Em sẽ gặp lại ý này nhiều lần trong số học và trong toán modulo.Ứng dụng: tính $100!$ và $2^{1000}$. Giai thừa $n! = 1 \cdot 2 \cdot 3 \cdots n$ lớn cực nhanh: $20!$ còn vừa long long, $21!$ đã tràn, còn $100!$ có tới 158 chữ số. Nhưng mỗi bước ta chỉ nhân số lớn hiện tại với một số nhỏ $x \le n$, đúng phép nhân số lớn với số nhỏ ở phần 4. Lần này mình lưu bằng mảng đảo ngược d (d[0] là hàng đơn vị) để kết quả dài thêm thì chỉ việc push_back:
Xem code C++ / Python: tính n! bằng mảng chữ số đảo ngược (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
vector<int> d = {1}; // d[0] là hàng đơn vị; ban đầu số 1
for(int x = 2; x <= n; x++){ // nhân dần với 2, 3, ..., n
long long nho = 0;
for(int i = 0; i < (int)d.size(); i++){
long long s = (long long)d[i] * x + nho;
d[i] = s % 10;
nho = s / 10;
}
while(nho > 0){ d.push_back(nho % 10); nho /= 10; }
}
for(int i = d.size() - 1; i >= 0; i--) cout << d[i]; // in ngược lại
return 0;
}n = int(input())
f = 1
for x in range(2, n + 1): # Python tự lo số lớn, chỉ việc nhân
f *= x
print(f)Tương tự, $2^{1000}$ chỉ là nhân đôi 1000 lần liên tiếp, mỗi lần là một phép nhân số lớn với số nhỏ $k = 2$. Kết quả có 302 chữ số, tổng các chữ số là 1366 (em sẽ tự làm ở bài tập 8). Trong Python, cả hai việc chỉ là một dòng: print(math.factorial(100)) và print(2 ** 1000).
int của Python không bao giờ tràn: a + b, a - b, a * b, a // k, a % k, a ** n đều đúng với số hàng nghìn chữ số. Tuy nhiên từ Python 3.11, việc đổi xâu sang số (int(s)) hoặc in số ra (str(x), print(x)) sẽ báo lỗi nếu số dài hơn 4300 chữ số. Khi đề cho số rất dài, em thêm hai dòng này ở đầu chương trình:import sys
if hasattr(sys, 'set_int_max_str_digits'):
sys.set_int_max_str_digits(0) # 0 = bỏ giới hạnint khá chậm (cỡ một giây). Nếu chỉ cần số dư thì duyệt từng chữ số như trên vẫn nhanh hơn.| Phép tính | Hướng đi | Mang theo | Độ phức tạp | Python |
|---|---|---|---|---|
| So sánh | độ dài, rồi trái → phải | (không) | $O(n)$ | a < b |
| Cộng | phải → trái | nhớ 0 hoặc 1 | $O(n)$ | a + b |
| Trừ ($a \ge b$) | phải → trái | mượn 0 hoặc 1 | $O(n)$ | a - b |
| Nhân với số nhỏ $k$ | phải → trái | nhớ có thể lớn | $O(n)$ | a * k |
| Nhân hai số lớn | mọi cặp $(i, j)$ vào ô $i + j$ | xử lý nhớ một lượt cuối | $O(n \cdot m)$ | a * b |
| Chia cho số nhỏ $k$ | trái → phải | phần dư $r < k$ | $O(n)$ | a // k, a % k |
Bảng 7. Tóm tắt các phép tính số lớn. $n$, $m$ là số chữ số. Mọi phép (trừ so sánh và chia) cần thêm bước bỏ số 0 ở đầu kết quả.
Khi đi thi: trước khi lao vào số lớn, em hãy ước lượng đáp án có vừa long long không. Nhiều bài trông “to” nhưng chỉ hỏi số dư (dùng phép đồng dư), hoặc đáp án chỉ tới $10^{18}$ (dùng long long là đủ). Chỉ khi đề thật sự yêu cầu in ra toàn bộ một số quá 19 chữ số thì mới cần cài số lớn. Nếu thi bằng Python thì cứ dùng int, nhớ bỏ giới hạn 4300 chữ số.
- Giai Thừa (n < 23) (Dễ)
- Tìm Số Đảo Ngược (VL18) (Dễ)
- Rotate Numbers (NTHU OJ 12934) (Dễ)
- Đường Đi Của Robot (ROBOT) (Trung bình)
- Tính tổng (OLP2B) (Khá)
- Chú Tiểu Chùa Hương (Khá)
Bài tậpLuyện số nguyên lớn
Cho hai số tự nhiên $a$ và $b$, mỗi số có không quá $10^5$ chữ số và không có chữ số 0 thừa ở đầu. Hãy in ra $a + b$.
99999999999999999999 1100000000000000000000📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
cong ở phần 2: cộng từng cột từ phải sang trái, nhớ s / 10, viết s % 10, cuối cùng đảo ngược. Ở ví dụ, hai mươi chữ số 9 cộng 1: cột nào cũng được 10, viết 0 nhớ 1, và hết chữ số vẫn còn nhớ 1 nên kết quả có 21 chữ số. Với Python, chỉ cần print(int(a) + int(b)), nhưng nhớ bỏ giới hạn 4300 chữ số vì số có tới $10^5$ chữ số.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
string cong(string a, string b){
string res = "";
int i = a.size() - 1, j = b.size() - 1, nho = 0;
while(i >= 0 || j >= 0 || nho > 0){ // còn chữ số hoặc còn nhớ
int s = nho;
if(i >= 0) s += a[i--] - '0'; // chữ số của a ở cột này
if(j >= 0) s += b[j--] - '0'; // chữ số của b ở cột này
res += char(s % 10 + '0'); // viết hàng đơn vị của s
nho = s / 10; // nhớ sang cột bên trái
}
reverse(res.begin(), res.end()); // ta viết từ hàng đơn vị nên phải đảo lại
return res;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
string a, b;
cin >> a >> b;
cout << cong(a, b);
return 0;
}import sys
if hasattr(sys, 'set_int_max_str_digits'):
sys.set_int_max_str_digits(0) # bỏ giới hạn 4300 chữ số (Python 3.11+)
a, b = sys.stdin.read().split()
print(int(a) + int(b))Cho hai số tự nhiên $a$ và $b$, mỗi số có không quá $10^5$ chữ số. Lưu ý: số có thể có các chữ số 0 thừa ở đầu (ví dụ 00123 chính là 123). In ra <, > hoặc = tuỳ theo $a$ nhỏ hơn, lớn hơn hay bằng $b$.
000123 99>📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
(len(a), a) với (len(b), b), vì Python so sánh cặp theo phần tử đầu trước. Dùng int(a) < int(b) cũng đúng, nhưng phải bỏ giới hạn 4300 chữ số và chậm hơn.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
string chuanHoa(string s){
int p = 0;
while(p + 1 < (int)s.size() && s[p] == '0') p++;
return s.substr(p);
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
string a, b;
cin >> a >> b;
a = chuanHoa(a); b = chuanHoa(b);
if(a.size() != b.size()) cout << (a.size() < b.size() ? "<" : ">");
else if(a == b) cout << "=";
else cout << (a < b ? "<" : ">");
return 0;
}import sys
a, b = sys.stdin.read().split()
a = a.lstrip('0') or '0'
b = b.lstrip('0') or '0'
x, y = (len(a), a), (len(b), b) # so độ dài trước, rồi so từ điển
print('<' if x < y else ('>' if x > y else '='))Cho hai số tự nhiên $a$ và $b$ (mỗi số không quá $10^5$ chữ số, không có số 0 thừa ở đầu). In ra $a - b$. Kết quả có thể âm.
100 1000-900📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
tru(a, b), ngược lại in dấu - rồi đến tru(b, a). Đừng quên bỏ số 0 ở đầu kết quả: $1000 - 100 = 0900 \to 900$. Và khi $a = b$ phải in 0, không in -0 hay xâu rỗng. Python: print(int(a) - int(b)) tự xử lý cả dấu âm.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
string chuanHoa(string s){
int p = 0;
while(p + 1 < (int)s.size() && s[p] == '0') p++;
return s.substr(p);
}
int soSanh(string a, string b){
a = chuanHoa(a); b = chuanHoa(b);
if(a.size() != b.size()) return a.size() < b.size() ? -1 : 1;
if(a == b) return 0;
return a < b ? -1 : 1;
}
string tru(string a, string b){ // yêu cầu a >= b
string res = "";
int i = a.size() - 1, j = b.size() - 1, muon = 0;
while(i >= 0){
int s = (a[i--] - '0') - muon;
if(j >= 0) s -= b[j--] - '0';
if(s < 0){ s += 10; muon = 1; } // không đủ trừ: mượn 1 chục
else muon = 0;
res += char(s + '0');
}
while(res.size() > 1 && res.back() == '0') // bỏ số 0 ở đầu (đang nằm ở cuối res)
res.pop_back();
reverse(res.begin(), res.end());
return res;
}
int main(){
string a, b;
cin >> a >> b;
a = chuanHoa(a); b = chuanHoa(b);
if(soSanh(a, b) >= 0) cout << tru(a, b);
else cout << "-" << tru(b, a); // a < b: a - b = -(b - a)
return 0;
}import sys
if hasattr(sys, 'set_int_max_str_digits'):
sys.set_int_max_str_digits(0)
a, b = sys.stdin.read().split()
print(int(a) - int(b)) # Python tự xử lý cả số âmCho số tự nhiên $a$ có không quá $10^5$ chữ số và số nguyên $k$ ($0 \le k \le 10^9$). In ra $a \cdot k$.
99999999999999999999 999899999999999999999901📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
nhanNho ở phần 4: mỗi cột tính s = chữ số × k + nhớ. Số nhớ có thể tới gần $10^9$, nên hết chữ số rồi phải dùng vòng while viết nốt từng chữ số của nhớ, và mọi biến phải là long long. Trường hợp $k = 0$ hoặc $a = 0$ phải in đúng 0. Ví dụ: $(10^{20} - 1) \cdot 99 = 99 \cdot 10^{20} - 99$.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
string nhanNho(string a, long long k){ // a là số lớn, 0 <= k <= 10^9
if(k == 0) return "0";
string res = "";
long long nho = 0;
for(int i = a.size() - 1; i >= 0; i--){
long long s = (a[i] - '0') * k + nho; // cả chữ số nhân với k, cộng nhớ
res += char(s % 10 + '0');
nho = s / 10; // nhớ có thể lớn hơn 9!
}
while(nho > 0){ // viết nốt phần nhớ còn lại
res += char(nho % 10 + '0');
nho /= 10;
}
reverse(res.begin(), res.end());
return res;
}
int main(){
string a; long long k;
cin >> a >> k;
cout << nhanNho(a, k);
return 0;
}import sys
if hasattr(sys, 'set_int_max_str_digits'):
sys.set_int_max_str_digits(0)
a, k = sys.stdin.read().split()
print(int(a) * int(k))Cho số tự nhiên $a$ có không quá $10^6$ chữ số và số nguyên $k$ ($1 \le k \le 10^9$). In ra số dư khi chia $a$ cho $k$.
123456789123456789 110📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
r = (r * 10 + c) % k (mẹo cuối phần 5). Vì $r < k \le 10^9$ nên $r \cdot 10 + c$ vừa long long. Python có thể viết int(a) % k, nhưng đổi xâu một triệu chữ số sang số vừa phải bỏ giới hạn 4300 chữ số vừa mất cỡ một giây, nên duyệt từng chữ số an toàn hơn.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
string a; long long k;
cin >> a >> k;
long long r = 0;
for(char c : a) r = (r * 10 + (c - '0')) % k; // chỉ giữ phần dư
cout << r;
return 0;
}import sys
a, k = sys.stdin.read().split()
k = int(k)
r = 0
for ch in a: # giống chia số lớn, nhưng không cần thương
r = (r * 10 + ord(ch) - 48) % k
print(r)Cho số nguyên $n$ ($0 \le n \le 500$). In ra giá trị chính xác của $n! = 1 \cdot 2 \cdots n$ (quy ước $0! = 1$).
2515511210043330985984000000📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
push_back. $500!$ có 1135 chữ số, mỗi lần nhân duyệt hết mảng nên tổng chỉ cỡ $500 \cdot 1135$ phép tính. Python: nhân int bình thường, hoặc math.factorial(n).Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
vector<int> d = {1}; // d[0] là hàng đơn vị; ban đầu số 1
for(int x = 2; x <= n; x++){ // nhân dần với 2, 3, ..., n
long long nho = 0;
for(int i = 0; i < (int)d.size(); i++){
long long s = (long long)d[i] * x + nho;
d[i] = s % 10;
nho = s / 10;
}
while(nho > 0){ d.push_back(nho % 10); nho /= 10; }
}
for(int i = d.size() - 1; i >= 0; i--) cout << d[i]; // in ngược lại
return 0;
}n = int(input())
f = 1
for x in range(2, n + 1):
f *= x
print(f) # 500! có 1135 chữ số, vẫn dưới giới hạn 4300 khi inCho hai số tự nhiên $a$ và $b$, mỗi số có không quá $2000$ chữ số (không có số 0 thừa ở đầu). In ra $a \cdot b$.
12345678901234567890 987654321098765432101219326311370217952237463801111263526900📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
a[i] * b[j] vào res[i + j], cuối cùng xử lý nhớ một lượt và bỏ số 0 ở đầu. Tổng cộng $2000 \cdot 2000 = 4 \cdot 10^6$ phép nhân. Nhớ trường hợp một số bằng 0: kết quả phải là 0 chứ không phải 0000. Python: int(a) * int(b), tích có thể tới 4000 chữ số nên vẫn nên bỏ giới hạn 4300 cho chắc.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
string nhan(string a, string b){
int n = a.size(), m = b.size();
vector<long long> res(n + m, 0);
for(int i = 0; i < n; i++) // a[n-1-i] là chữ số hàng 10^i của a
for(int j = 0; j < m; j++) // b[m-1-j] là chữ số hàng 10^j của b
res[i + j] += (a[n - 1 - i] - '0') * (b[m - 1 - j] - '0');
for(int k = 0; k + 1 < n + m; k++){ // xử lý nhớ một lượt từ hàng đơn vị
res[k + 1] += res[k] / 10;
res[k] %= 10;
}
int k = n + m - 1;
while(k > 0 && res[k] == 0) k--; // bỏ số 0 ở đầu
string s = "";
for(; k >= 0; k--) s += char(res[k] + '0');
return s;
}
int main(){
string a, b;
cin >> a >> b;
cout << nhan(a, b);
return 0;
}import sys
if hasattr(sys, 'set_int_max_str_digits'):
sys.set_int_max_str_digits(0)
a, b = sys.stdin.read().split()
print(int(a) * int(b))Cho số nguyên $n$ ($0 \le n \le 30000$). Gọi $X = 2^n$. In ra hai số: số chữ số của $X$ và tổng các chữ số của $X$.
155 26📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
{1}, nhân đôi $n$ lần (nhân số lớn với số nhỏ $k = 2$, nhớ chỉ là 0 hoặc 1). $2^{30000}$ có 9031 chữ số, tổng số phép tính cỡ $30000 \cdot 9031 / 2 \approx 1{,}4 \cdot 10^8$, C++ chạy chưa tới nửa giây. (Muốn nhanh hơn nữa, có thể nhân với $2^{20}$ mỗi lần, hoặc lưu mỗi ô 9 chữ số.) Python làm được trong một dòng str(2 ** n), nhưng $9031 > 4300$ chữ số nên bắt buộc phải bỏ giới hạn, nếu không chương trình báo lỗi ValueError.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n;
vector<int> d = {1}; // d[0] là hàng đơn vị
for(int t = 0; t < n; t++){ // nhân đôi n lần
int nho = 0;
for(int i = 0; i < (int)d.size(); i++){
int s = d[i] * 2 + nho;
d[i] = s % 10;
nho = s / 10;
}
if(nho) d.push_back(nho);
}
int tong = 0;
for(int x : d) tong += x;
cout << d.size() << " " << tong;
return 0;
}import sys
if hasattr(sys, 'set_int_max_str_digits'):
sys.set_int_max_str_digits(0) # 2^30000 có 9031 chữ số
n = int(input())
s = str(2 ** n)
print(len(s), sum(map(int, s)))
- 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