# Cộng, trừ, nhân 2 số nguyên lớn
**1. Cộng 2 số nguyên lớn**

**Bước 1**: Chuẩn hóa 2 xâu a và b để 2 xâu có độ dài bằng nhau. Xâu nào ngắn hơn thì ta thêm ký tự ‘0’ vào đầu xâu đó cho đến khi 2 xâu có độ dài bằng nhau thì dừng.

**Bước 2**: Duyệt từ cuối xâu về đầu xâu:
* Khởi tạo 1 biến lưu kết quả **ans**.
* Xét từng ký tự chuyển sang kiểu **int** xong cộng lại và lưu vào biến **sum**, đồng thời khởi tạo biến **carry** để nhớ 1 (trong trường hợp hai số cộng lại lớn hơn 9).

**Tổng quát:**
* **ans = a;** *// Gán a cho ans*
* for(int i từ cuối về đầu)
* **sum = a – ‘0’ + b – ‘0’ + carry;** *// Cộng 2 số, để chuyển kiểu ký tự sang int thì ta trừ đi ‘0’ hoặc 48.*
* **carry = sum / 10;** *// Nếu sum > 9 thì chia 10 chắc chắn được 1.*
* **ans[i] = (sum % 10) + ‘0’;** *// (sum % 10) là số vừa được tính, sau đó + '0' để chuyển sang kiểu ký tự*

**Ví dụ:**

**string** a = “15”; **string** b = “89”;

❖ **for lần 1** (i = 1), **carry** lúc đầu = 0, **ans** = **a** = “15”:
* sum = 5 - ‘0’ + 9 - ‘0’ + 0 = 14;
* carry = 14 / 10 = 1;
* ans[1] = (14 % 10) + ‘0’ = 4;
**=>** ans lúc này = “14”.

❖ **for lần 2** (i = 0), **carry** lúc này = 1, **ans** = “14”:
* sum = 1 - ‘0’ + 8 - ‘0’ + 1 = 10;
* carry = 10 / 10 = 1;
* ans[0] = (10 % 10) + ‘0’ = 0;
**=>** ans lúc này = “04”.

Tới đây thì rõ ràng là **carry** vẫn còn đang nhớ 1, nên ta phải thêm 1 bước xử lí nữa để kiểm tra xem nếu **carry = 1** thì ta thêm ký tự **‘1’** vào trước xâu **ans**. Cuối cùng ta thu được kết quả là **ans = “104”** là kết quả của bài toán.

**Code mẫu:**

// author: hatakaze (a.k.a Tran Gia Huy)
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

string add_num(string a, string b) {
    ll carry = 0, sum;
    string ans;
    // Xử lí để hai xâu a và b có độ dài bằng nhau
    for(int i = 0; i < max(a.size(), b.size()); i++) {
        if(a.size() == b.size()) break; // Nếu bằng nhau thì dừng
        else if(a.size() < b.size()) {
            a = '0' + a;
        }
        else {
            b = '0' + b;
        }
    }
    // Lưu ý gán a cho ans sau khi cả 2 xâu a và b đã có độ dài bằng nhau
    ans = a;
    for(int i = a.size() - 1; i >= 0; i--) {
        sum = a[i] - '0' + b[i] - '0' + carry; // - ‘0’ để chuyển từ chuỗi sang số
        carry = sum / 10;
        ans[i] = (sum % 10) + '0'; // + ‘0’ để chuyển từ số sang chuỗi
    }
    if(carry == 1) ans = '1' + ans; // Nếu nhớ = 1 thì thêm ‘1’ vào trước ans
    return ans;
}
int main() {
    string a, b; cin >> a >> b;
    cout << add_num(a, b);
}

\
**2. Trừ 2 số nguyên lớn (Số lớn trừ số bé)**
Các bước đầu tương tự ở phần 1 nhưng sẽ khác một chút. Ở dạng trừ này thì sẽ có trường hợp như là 10 – 06 = 04 nên ta cần phải bỏ đi số 0 vô nghĩa kia để ra được đáp án cuối cùng là 4.

**Tổng quát:**
* **ans = a** *// Gán a cho ans*
* for(int i từ **cuối** về **đầu**):
* **sum = (a – ‘0’) – (b – ‘0’) – carry;**
* **if(sum < 0)** thì ta sẽ làm 2 thao tác:
* **sum += 10;** *// Khi đã chạy dòng này nghĩa là sum tính ra số âm, nên ta phải mượn 1 chèn vào phía trước, nghĩa là +10 vào số đó.*
* **carry = 1;** *// Nhớ 1*
* **else** thì chỉ cần cho **carry = 0**;
* **ans[i] = sum + ‘0’;** *// Chuyển từ kiểu int sang ký tự*

Như đã nói ở trên, ta thêm vào bước xử lý số 0 vô nghĩa:
> **while**(ans.size() > 1 && ans[0] == '0') ans.erase(0, 1);
> [color=#138ec6]

**Giải thích**: Dòng này có nghĩa là chỉ khi **ans** có độ dài từ 2 trở lên (ví dụ **ans** = “04” thì ans.size() khi này = 2) và ký tự đầu tiên của **ans** = ‘0’ thì dòng ans.erase(0, 1) **(VariableName.erase(iterator_first, iterator_last))** sẽ xóa đi 1 ký tự từ vị trí 0.

Giả sử ta có chuỗi **“0000019”** thì vòng **while** sẽ lặp 5 lần, mỗi lần sẽ xóa đi 1 ký tự ở đầu:
**Lần 1:** “000019”;
**Lần 2:** “00019”;
**Lần 3:** “0019”;
**Lần 4:** “019”;
**Lần 5:** “19”;

**Ví dụ:**
**string** a = “55”; **string** b = “19”;

❖ **for lần 1** (i = 1), **carry** lúc đầu = 0, **ans** = **a** = “55”:
* sum = 5 - ‘0’ – 9 - ‘0’ – 0 = -4;
* if(sum < 0) mệnh đề đúng {
* sum = sum + 10 = -4 + 10 = 6;
* carry = 1; // *update carry*
* else *vì đã chạy if ở trên nên else được bỏ qua:* { carry = 0; }
* ans[1] = sum + ‘0’ = ‘6’;
**=>** ans lúc này = “56”

❖ **for lần 2** (i = 0), **carry** lúc này = 1, **ans** = “56”:
* sum = 5 - ‘0’ – 1 - ‘0’ – 1 = 3;
* if(sum < 0) *// mệnh đề sai -> không được chạy*
* sum += 10;
* carry = 1;
* else *// vì if ở trên không được chạy nên else sẽ được chạy* { carry = 0; }
* ans[0] = sum + ‘0’ = ‘3’;
**=>** ans lúc này = “36”

**Code mẫu:**

string sub_num(string a, string b) {
    ll carry = 0, sum;
    string ans;
    // Xử lí để hai xâu a và b có độ dài bằng nhau
    for(int i = 0; i < max(a.size(), b.size()); i++) {
        if(a.size() == b.size()) break; // Nếu bằng nhau thì dừng
        else if(a.size() < b.size()) {
            a = '0' + a;
        }
        else {
            b = '0' + b;
        }
    }
    ans = a;
    for(int i = a.size() - 1; i >= 0; i--) {
        sum = (a[i] - '0') - (b[i] - '0') – carry;
        if(sum < 0) {
            sum += 10;
            // Đồng thời biến nhớ sẽ gán cho = 1
            carry = 1;
        }
        else carry = 0;
        ans[i] = (sum + '0');
    }
    while(ans.size() > 1 && ans[0] == '0') ans.erase(0, 1);
    return ans;
}

\
**3. Nhân 2 số nguyên lớn**
Ở đây ta sẽ sử dụng **thuật toán nhân với số nhỏ** và **thuật toán cộng hai số** (Lưu ý: trước khi cộng hai xâu, ta thêm ký tự ‘0’ vào cuối xâu thứ hai).

// Thuật toán nhân với số nhỏ
string small_mul(string a, int k) {
    ll carry = 0, sum;
    string ans = a;
    for(int i = a.size() - 1; i >= 0; i--) {
        sum = (a[i] - '0') * k + carry;
        carry = sum / 10; // Đối với nhân thì nhớ có thể lên đến 8
    	ans[i] = (sum % 10 + '0');
    }
    if(carry != 0) { // Phải để là != vì có thể carry là một số lớn hơn 1
		ans = char(carry + '0') + ans;
	}
    while(ans.size() > 1 && ans[0] == '0') ans.erase(0, 1);
    return ans;
}

// Thuật toán cộng hai số
string add_num(string a, string b) {
    ll carry = 0, sum;
    string ans;
    // Lưu ý gán a cho ans sau khi cả 2 xâu a và b đã có độ dài bằng nhau
    ans = a;
    for(int i = a.size() - 1; i >= 0; i--) {
        sum = a[i] - '0' + b[i] - '0' + carry; // - ‘0’ để chuyển từ chuỗi sang số
        carry = sum / 10;
        ans[i] = (sum % 10) + '0'; // + ‘0’ để chuyển từ số sang chuỗi
    }
    if(carry == 1) ans = '1' + ans; // Nếu nhớ = 1 thì thêm ‘1’ vào trước ans
    return ans;
}

Biến **ans** để lưu kết quả cuối cùng, **ax** để lưu kết quả mỗi lần cộng hai số, **bx** để lưu kết quả mỗi lần nhân hai số nhỏ, **tight** mỗi lần lặp sẽ +1 lên tương ứng với số lượng ký tự ‘0’ được thêm vào.

// Hàm tính toán nhân 2 số nguyên lớn thông qua 2 hàm trên
string big_mul(string a, string b) {
    string ans, ax = "0", bx;
    int tight = 0;
    for(int i = b.size() - 1; i >= 0; i--) {
        bx = small_mul(a, b[i] - '0');
        bx.insert(bx.size(), tight, '0');
        ++tight;
        ans = add_num(ax, bx);
        ax = ans;
    }
    return ans;
}

\
**Giải thích:**
+ **Dòng 4:** ta duyệt từ cuối về đầu như thông thường.
+ **Dòng 5:** **bx** sẽ lưu kết quả của số ở vị trí cuối trong xâu b nhân lần lượt với từng số trong xâu a. Ví dụ ở đây ta thấy số 2 sẽ nhân lần lượt với các số ở hàng trên, sau đó sẽ là số 1 nhân lần lượt với các hàng ở trên. Sau đó ta sẽ có những hàng phía dưới, việc ta cần làm là cộng hết vô theo hàng dọc.

+ **Dòng 6:** thêm ký tự ‘0’ vào sau xâu (vòng lặp đầu tiên sẽ không được thêm), sau đó biến **tight** được tăng lên 1 nghĩa là những lần lặp sau đó sẽ thêm ký tự ‘0’ vào sau xâu tương ứng với giá trị của **tight**.
+ **Dòng 8:** biến **ans** sẽ lưu tổng của số được nhân (tổng của **ax** và **bx**), ban đầu ta cho **ax = “0”**, sau đó tính được **bx**, thì kết quả này sẽ được lưu lại. Sau đó, **dòng 9** ta sẽ gán lại giá trị **ans** cho **ax**. Ví dụ, ban đầu **ax = “0”**, **bx** tính được là **“123”**, thì **ans** sẽ là tổng của 2 xâu đó (**= “123”**). Xong gán lại kết quả đó cho **ax** (**= “123”**), rồi ta lại tính lần tiếp theo được **bx = “333”**, thì ta lại gán tổng của chúng cho **ans** (**= “456”**) và gán kết quả này cho **ax** (**= “456”**) và cứ theo thứ tự như thế sau vòng lặp cuối cùng ta sẽ có kết quả thu được vào biến **ans**.

//author : hatakaze (a.k.a Tran Gia Huy)
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

string add_num(string a, string b) {
    ll carry = 0, sum;
    string ans;
    for(int i = 0; i < max(a.size(), b.size()); i++) {
        if(a.size() == b.size()) break;
        else if(a.size() < b.size()) {
        	a = '0' + a;
        }
        else {
        	b = '0' + b;
        }
    }
    ans = a;
    for(int i = a.size() - 1; i >= 0; i--) {
        sum = a[i] - '0' + b[i] - '0' + carry;
        carry = sum / 10;
        ans[i] = (sum % 10) + '0';
    }
    if(carry == 1) ans = '1' + ans;
    return ans;
}
string small_mul(string a, int k) {
    ll carry = 0, sum;
    string ans = a;
    for(int i = a.size() - 1; i >= 0; i--) {
        sum = (a[i] - '0') * k + carry;
        carry = sum / 10;
    	ans[i] = (sum % 10 + '0');
    }
    if(carry != 0) { // Phải để là != vì có thể carry là một số lớn hơn 1
	ans = char(carry + ‘0’) + ans;
    }
    while(ans.size() > 1 && ans[0] == '0') ans.erase(0, 1);
    return ans;
}
string big_mul(string a, string b) {
    string ans, ax = "0", bx;
    int tight = 0;
    for(int i = b.size() - 1; i >= 0; i--) {
        bx = small_mul(a, b[i] - '0');
        bx.insert(bx.size(), tight, '0');
        ++tight;
        ans = add_num(ax, bx);
        ax = ans;
    }
    return ans;
}

void solve() {
    string a, b; cin >> a >> b;
    cout << big_mul(a, b) << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    solve();
    return 0;
}