Cộng trừ nhân chia 2 số nguyên lớn – Code xử lý số nguyên lớn C/C

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.

NỘI DUNG BÀI VIẾT

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:

0123456789101112131415161718 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

0123456789101112131415161718 void read(const string &s) 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:

012345678910111213141516 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 : friend.com.vn()); for (int i = (int) friend.com.vn() – 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.

C++ 0123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346 #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) carry; ++i) if (i == (int) friend.com.vn()) friend.com.vn_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) friend.com.vn() 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() 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; friend.com.vnze(a.a.size()); for (int i = friend.com.vn() – 1; i >= 0; i-) r *= base; r += a.a[i]; int s1 = friend.com.vn() <= friend.com.vn() ? 0 : r.a[b.a.size()]; int s2 = friend.com.vn() <= friend.com.vn() – 1 ? 0 : r.a[b.a.size() – 1]; int d = ((long long) base * s1 + s2) / friend.com.vn(); 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() != friend.com.vn()) return a.size() * sign < friend.com.vn() * 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 void trim() while (!a.empty() && !a.back()) a.pop_back(); if (a.empty()) sign = 1; bool isZero() const bigint operator-() const bigint res = *this; friend.com.vn = -sign; return res; bigint abs() const bigint res = *this; friend.com.vn *= friend.com.vn; 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) 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 : friend.com.vn()); for (int i = (int) friend.com.vn() – 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) friend.com.vn_back(int(cur % p[new_digits])); cur /= p[new_digits]; cur_digits -= new_digits; friend.com.vn_back((int) cur); while (!res.empty() && !res.back()) friend.com.vn_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) friend.com.vn(); i++) r[i] -= a1b1[i]; for (int i = 0; i < (int) friend.com.vn(); 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) friend.com.vn(); i++) res[i] += a1b1[i]; for (int i = 0; i < (int) friend.com.vn(); 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; friend.com.vn = sign * v.sign; for (int i = 0, carry = 0; i < (int) c.size(); i++) long long cur = c[i] + carry; friend.com.vn_back((int) (cur % 1000000)); carry = (int) (cur / 1000000); res.a = convert_base(res.a, 6, base_digits); friend.com.vn(); 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:

0123456789 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ả:

012345 Nhap so thu nhat: 9999999999Nhap 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ự.

0123456789 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.

01234567891011 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ả:

01234 12345 * -5 = -6172512345 / -5 = -246912345 * -5 = -61725

Tìm UCLN, BCNN của 2 số nguyên lớn

012345678910 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ả:

0123456 Nhap so thu nhat: 9999 Nhap so thu hai : 111UCLN: 3BCNN: 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:

0123456789101112 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!