Cộng trừ nhân chia 2 số nguyên lớn trong C/C++ là chủ đề của bài viết này. Nguyễn Văn Hiếu Blog sẽ cung cấp cho các bạn phương pháp để thao tác với số nguyên lớn trong ngôn ngữ lập trình C/C++. Các phép toán cơ bản đối với số nguyên lớn bao gồm: cộng trừ nhân chia 2 số nguyên lớn, và một số phép toán khác nữa.
1. Khi nào cần Bigint trong C/C++?
Bài toán 1:
Cho hai số nguyên dương A và B ( A & B có không quá 1000 chữ số )
Yêu cầu: Tính A + B, A – B, A * B
Các bạn có thể làm thử bài tập này và chấm điểm lời giải của bạn tại đây
Bài toán 2:
Cho số nguyên dương N(N <= 1000). Hãy tính N!
Bàn luận về số nguyên lớn:
Nếu không quan tâm tới phạm vi giá trị của các biến trong 2 bài tập trên. Thì đây là những bài tập cực kỳ đơn giản. Tuy nhiên, nếu bạn code sẽ gặp phải hiện tượng lỗi tràn số.
Nếu bạn chưa biết tràn số là gì? phạm vi giá trị các kiểu dữ liệu là gì, vui lòng đọc trước bài viết này trước khi tiếp tục.
Chúng ta sẽ cần làm việc và quan tâm tới big number khi các kiểu dữ liệu thông thường không thể lưu được những giá trị quá lớn. Khi đó, chúng ta cần xây dựng một chương trình thao tác với số nguyên lớn.
Tôi sẽ cung cấp lời giải 2 ví dụ trên cho bài toán số nguyên lớn của chúng ta ở mục cuối của bài này.
2. Thao tác với số nguyên lớn trong C/C++
Đầu tiên, chúng ta sẽ khai báo cấu trúc struct như sau:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
const int base = 1000000000; const int base_digits = 9; struct bigint { vector<int> a; int sign; bigint() : sign(1) { } bigint(long long v) { *this = v; } bigint(const string &s) { read(s); } } |
Trong đó, sign lưu dấu(số âm, dương) của số nguyên lớn. Mỗi phần tử của vector a sẽ lưu một đoạn của số nguyên lớn – đoạn đó nhiều nhất sẽ có 9 chữ số. Như vậy, 1 số nguyên lớn có 90 chữ số chỉ cần vector có size = 10.
Tiếp đó là một số hàm tạo nhận các đối số khác nhau cho kiểu dữ liệu bigint của chúng ta.
Tiếp theo là hàm chuyển string sang số nguyên lớn
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
void read(const string &s) { sign = 1; a.clear(); int pos = 0; while (pos < (int) s.size() && (s[pos] == '-' || s[pos] == '+')) { if (s[pos] == '-') sign = -sign; ++pos; } for (int i = s.size() - 1; i >= pos; i -= base_digits) { int x = 0; for (int j = max(pos, i - base_digits + 1); j <= i; j++) x = x * 10 + s[j] - '0'; a.push_back(x); } trim(); } |
Nạp chồng các toán tử nhập và xuất:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
friend istream& operator>>(istream &stream, bigint &v) { string s; stream >> s; v.read(s); return stream; } friend ostream& operator<<(ostream &stream, const bigint &v) { if (v.sign == -1) stream << '-'; stream << (v.a.empty() ? 0 : v.a.back()); for (int i = (int) v.a.size() - 2; i >= 0; --i) stream << setw(base_digits) << setfill('0') << v.a[i]; return stream; } |
Và nạp chồng một loạt các toán tử khác bao gồm: +, -, *, /, %, +=, -=, *=, /=,…
3. Tự code thư viện thao tác với số nguyên lớn
Dưới đây là full code xử lý số nguyên lớn trong C/C++. Code template này đã include đủ các thư viện cơ bản cần thiết. Việc của bạn là viết thêm hàm main và sử dụng nó.
Do vậy, lời giải ở các phần tiếp theo của bài viết này tôi chỉ đưa ra đoạn code của hàm main. Tôi giả sử rằng bạn đã đưa đoạn code này vào trước hàm main của tôi.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 |
#include <bits/stdc++.h> using namespace std; const int base = 1000000000; const int base_digits = 9; struct bigint { vector<int> a; int sign; bigint() : sign(1) { } bigint(long long v) { *this = v; } bigint(const string &s) { read(s); } void operator=(const bigint &v) { sign = v.sign; a = v.a; } void operator=(long long v) { sign = 1; if (v < 0) sign = -1, v = -v; for (; v > 0; v = v / base) a.push_back(v % base); } bigint operator+(const bigint &v) const { if (sign == v.sign) { bigint res = v; for (int i = 0, carry = 0; i < (int) max(a.size(), v.a.size()) || carry; ++i) { if (i == (int) res.a.size()) res.a.push_back(0); res.a[i] += carry + (i < (int) a.size() ? a[i] : 0); carry = res.a[i] >= base; if (carry) res.a[i] -= base; } return res; } return *this - (-v); } bigint operator-(const bigint &v) const { if (sign == v.sign) { if (abs() >= v.abs()) { bigint res = *this; for (int i = 0, carry = 0; i < (int) v.a.size() || carry; ++i) { res.a[i] -= carry + (i < (int) v.a.size() ? v.a[i] : 0); carry = res.a[i] < 0; if (carry) res.a[i] += base; } res.trim(); return res; } return -(v - *this); } return *this + (-v); } void operator*=(int v) { if (v < 0) sign = -sign, v = -v; for (int i = 0, carry = 0; i < (int) a.size() || carry; ++i) { if (i == (int) a.size()) a.push_back(0); long long cur = a[i] * (long long) v + carry; carry = (int) (cur / base); a[i] = (int) (cur % base); //asm("divl %%ecx" : "=a"(carry), "=d"(a[i]) : "A"(cur), "c"(base)); } trim(); } bigint operator*(int v) const { bigint res = *this; res *= v; return res; } friend pair<bigint, bigint> divmod(const bigint &a1, const bigint &b1) { int norm = base / (b1.a.back() + 1); bigint a = a1.abs() * norm; bigint b = b1.abs() * norm; bigint q, r; q.a.resize(a.a.size()); for (int i = a.a.size() - 1; i >= 0; i--) { r *= base; r += a.a[i]; int s1 = r.a.size() <= b.a.size() ? 0 : r.a[b.a.size()]; int s2 = r.a.size() <= b.a.size() - 1 ? 0 : r.a[b.a.size() - 1]; int d = ((long long) base * s1 + s2) / b.a.back(); r -= b * d; while (r < 0) r += b, --d; q.a[i] = d; } q.sign = a1.sign * b1.sign; r.sign = a1.sign; q.trim(); r.trim(); return make_pair(q, r / norm); } bigint operator/(const bigint &v) const { return divmod(*this, v).first; } bigint operator%(const bigint &v) const { return divmod(*this, v).second; } void operator/=(int v) { if (v < 0) sign = -sign, v = -v; for (int i = (int) a.size() - 1, rem = 0; i >= 0; --i) { long long cur = a[i] + rem * (long long) base; a[i] = (int) (cur / v); rem = (int) (cur % v); } trim(); } bigint operator/(int v) const { bigint res = *this; res /= v; return res; } int operator%(int v) const { if (v < 0) v = -v; int m = 0; for (int i = a.size() - 1; i >= 0; --i) m = (a[i] + m * (long long) base) % v; return m * sign; } void operator+=(const bigint &v) { *this = *this + v; } void operator-=(const bigint &v) { *this = *this - v; } void operator*=(const bigint &v) { *this = *this * v; } void operator/=(const bigint &v) { *this = *this / v; } bool operator<(const bigint &v) const { if (sign != v.sign) return sign < v.sign; if (a.size() != v.a.size()) return a.size() * sign < v.a.size() * v.sign; for (int i = a.size() - 1; i >= 0; i--) if (a[i] != v.a[i]) return a[i] * sign < v.a[i] * sign; return false; } bool operator>(const bigint &v) const { return v < *this; } bool operator<=(const bigint &v) const { return !(v < *this); } bool operator>=(const bigint &v) const { return !(*this < v); } bool operator==(const bigint &v) const { return !(*this < v) && !(v < *this); } bool operator!=(const bigint &v) const { return *this < v || v < *this; } void trim() { while (!a.empty() && !a.back()) a.pop_back(); if (a.empty()) sign = 1; } bool isZero() const { return a.empty() || (a.size() == 1 && !a[0]); } bigint operator-() const { bigint res = *this; res.sign = -sign; return res; } bigint abs() const { bigint res = *this; res.sign *= res.sign; return res; } long long longValue() const { long long res = 0; for (int i = a.size() - 1; i >= 0; i--) res = res * base + a[i]; return res * sign; } friend bigint gcd(const bigint &a, const bigint &b) { return b.isZero() ? a : gcd(b, a % b); } friend bigint lcm(const bigint &a, const bigint &b) { return a / gcd(a, b) * b; } void read(const string &s) { sign = 1; a.clear(); int pos = 0; while (pos < (int) s.size() && (s[pos] == '-' || s[pos] == '+')) { if (s[pos] == '-') sign = -sign; ++pos; } for (int i = s.size() - 1; i >= pos; i -= base_digits) { int x = 0; for (int j = max(pos, i - base_digits + 1); j <= i; j++) x = x * 10 + s[j] - '0'; a.push_back(x); } trim(); } friend istream& operator>>(istream &stream, bigint &v) { string s; stream >> s; v.read(s); return stream; } friend ostream& operator<<(ostream &stream, const bigint &v) { if (v.sign == -1) stream << '-'; stream << (v.a.empty() ? 0 : v.a.back()); for (int i = (int) v.a.size() - 2; i >= 0; --i) stream << setw(base_digits) << setfill('0') << v.a[i]; return stream; } static vector<int> convert_base(const vector<int> &a, int old_digits, int new_digits) { vector<long long> p(max(old_digits, new_digits) + 1); p[0] = 1; for (int i = 1; i < (int) p.size(); i++) p[i] = p[i - 1] * 10; vector<int> res; long long cur = 0; int cur_digits = 0; for (int i = 0; i < (int) a.size(); i++) { cur += a[i] * p[cur_digits]; cur_digits += old_digits; while (cur_digits >= new_digits) { res.push_back(int(cur % p[new_digits])); cur /= p[new_digits]; cur_digits -= new_digits; } } res.push_back((int) cur); while (!res.empty() && !res.back()) res.pop_back(); return res; } typedef vector<long long> vll; static vll karatsubaMultiply(const vll &a, const vll &b) { int n = a.size(); vll res(n + n); if (n <= 32) { for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) res[i + j] += a[i] * b[j]; return res; } int k = n >> 1; vll a1(a.begin(), a.begin() + k); vll a2(a.begin() + k, a.end()); vll b1(b.begin(), b.begin() + k); vll b2(b.begin() + k, b.end()); vll a1b1 = karatsubaMultiply(a1, b1); vll a2b2 = karatsubaMultiply(a2, b2); for (int i = 0; i < k; i++) a2[i] += a1[i]; for (int i = 0; i < k; i++) b2[i] += b1[i]; vll r = karatsubaMultiply(a2, b2); for (int i = 0; i < (int) a1b1.size(); i++) r[i] -= a1b1[i]; for (int i = 0; i < (int) a2b2.size(); i++) r[i] -= a2b2[i]; for (int i = 0; i < (int) r.size(); i++) res[i + k] += r[i]; for (int i = 0; i < (int) a1b1.size(); i++) res[i] += a1b1[i]; for (int i = 0; i < (int) a2b2.size(); i++) res[i + n] += a2b2[i]; return res; } bigint operator*(const bigint &v) const { vector<int> a6 = convert_base(this->a, base_digits, 6); vector<int> b6 = convert_base(v.a, base_digits, 6); vll a(a6.begin(), a6.end()); vll b(b6.begin(), b6.end()); while (a.size() < b.size()) a.push_back(0); while (b.size() < a.size()) b.push_back(0); while (a.size() & (a.size() - 1)) a.push_back(0), b.push_back(0); vll c = karatsubaMultiply(a, b); bigint res; res.sign = sign * v.sign; for (int i = 0, carry = 0; i < (int) c.size(); i++) { long long cur = c[i] + carry; res.a.push_back((int) (cur % 1000000)); carry = (int) (cur / 1000000); } res.a = convert_base(res.a, 6, base_digits); res.trim(); return res; } }; |
4. Cộng trừ nhân chia 2 số nguyên lớn trong C/C++
4.1. Code cộng hai số nguyên lớn
Ở đoạn code template phía trên, tôi đã có ghi đè các toán tử + , +=, >> và <<. Do vậy, để cộng hai số nguyên lớn, ta làm đơn giản như sau:
|
1 2 3 4 5 6 7 8 |
int main(){ bigint n1, n2; cout << "\nNhap so thu nhat: "; cin >> n1; cout << "\nNhap so thu hai : "; cin >> n2; cout << "Tong 2 so = " << (n1 + n2) << '\n'; } |
Kết quả:
|
1 2 3 4 |
Nhap so thu nhat: 9999999999 Nhap so thu hai : -1111111111 Tong 2 so = 8888888888 |
4.2. Code trừ hai số nguyên lớn
Giống như phép toán cộng số nguyên lớn phía trên, phép trừ ta làm tương tự.
|
1 2 3 4 5 6 7 8 |
int main(){ bigint n1, n2; cout << "\nNhap so thu nhat: "; cin >> n1; cout << "\nNhap so thu hai : "; cin >> n2; cout << "Tong 2 so = " << (n1 - n2) << '\n'; } |
4.3. Một số phép toán với số nguyên lớn khác
Phép nhân chia 2 số nguyên lớn
Bạn có thể làm tương tự như phép cộng và trừ tôi đã làm ở trên. Còn dưới đây tôi sẽ thử sử dụng hàm tạo bigint từ biến string.
|
1 2 3 4 5 6 7 8 9 10 |
int main(){ string s1 = "12345", s2 = "-5"; bigint n1(s1), n2(s2); cout << s1 << " * " << s2 << " = " << (n1*n2) << '\n'; cout << s1 << " / " << s2 << " = " << (n1/n2) << '\n'; // Hoặc sử dụng toán tử '*=' // Sử dụng các toán tử +=, -=, /=, %= tương tự n1 *= n2; cout << s1 << " * " << s2 << " = " << n1 << '\n'; } |
Kết quả:
|
1 2 3 |
12345 * -5 = -61725 12345 / -5 = -2469 12345 * -5 = -61725 |
Tìm UCLN, BCNN của 2 số nguyên lớn
|
1 2 3 4 5 6 7 8 9 |
int main(){ bigint n1, n2; cout << "\nNhap so thu nhat: "; cin >> n1; cout << "\nNhap so thu hai : "; cin >> n2; cout << "UCLN: " << gcd(n1,n2) << '\n'; cout << "BCNN: " << lcm(n1,n2) << '\n'; } |
Kết quả:
|
1 2 3 4 5 |
Nhap so thu nhat: 9999 Nhap so thu hai : 111 UCLN: 3 BCNN: 369963 |
Ngoài ra, còn rất nhiều toán tử khác giúp chúng ta làm việc với số nguyên lớn. Ở đây tôi chỉ trình bày cộng trừ nhân chia 2 số nguyên lớn. Các bạn có thể tìm hiểu và sử dụng các hàm, toán tử khác có sẵn trong code template trên.
4.4. Bài toán tính giai thừa của số lớn
Với bài toán số 1, chính là bài toán cộng trừ nhân chia 2 số nguyên lớn. Và tôi đã giải quyết nó ở phía trên. Sau đây, chúng ta sẽ sử dụng template bigint trong c++ phía trên để tính giai thừa số nguyên lớn nhé.
Để tính giai thừa của số nguyên lớn, không có cách nào khác là nhân các phần tử từ 1,2,3,…,n với nhau. Tích của chúng sẽ là lời giải của bài toán này.
Với bài toán tính giai thừa của số nguyên lớn N(N <= 1000). Do đó, ta vẫn nhập N là số kiểu int nhé.
Sử dụng code template tôi cung cấp phía trên, và đây là hàm main chúng ta cần phải viết:
|
1 2 3 4 5 6 7 8 9 10 11 |
int main(){ bigint answer = 1; int N; cout << "Nhap so N = "; cin >> N; // Tinh giai thua for(int i = 2; i <= N; ++i){ answer *= i; } cout << N <<"! = " << answer << '\n'; } |
Và đây là ảnh chụp kết quả của phép tính 1000!
Kết luận
Như vậy, Nguyễn Văn Hiếu vừa cùng các bạn đi giải quyết hầu hết các bài toán cần xử lý với số nguyên lớn trong C/C++. Giờ đây, việc cộng trừ nhân chia 2 số nguyên lớn đã trở nên đơn giản hơn bao giờ hết khi chúng ta đã nạp chồng toán tử cho cấu trúc bigint. Hi vọng bài viết mang lại nhiều kiến thức bổ ích cho các bạn độc giả!
Chúc các bạn học tập tốt!
