Big Integer Addition

Given two positive integers (without leading zeros), calculate their sum.

Input Format
Two lines, each containing one integer.

Output Format
One line containing the resulting sum.

Constraints
$1 \leq \text{integer length} \leq 100000$

Example

Input:
12
23

Output:
35

Algorithm
Represent numbers as digit arrays in reverse order (least significant digit at index 0) to simplify carry propagation. Initialize a carry variable to 0. Iterate through both arrays simultaneously, adding corresponding digits and the carry. Store $digit % 10$ in the result and update carry to $digit / 10$. After the loop, if carry remains non-zero, append it to the result array.

Implementation

#include <iostream>
#include <vector>
#include <string>
using namespace std;

vector<int> addBigInt(vector<int>& lhs, vector<int>& rhs) {
    vector<int> result;
    int carry = 0;
    int maxLen = max(lhs.size(), rhs.size());
    
    for (int i = 0; i < maxLen; i++) {
        int sum = carry;
        if (i < lhs.size()) sum += lhs[i];
        if (i < rhs.size()) sum += rhs[i];
        result.push_back(sum % 10);
        carry = sum / 10;
    }
    
    if (carry) result.push_back(carry);
    return result;
}

int main() {
    string s1, s2;
    cin >> s1 >> s2;
    vector<int> num1, num2;
    
    for (int i = s1.length() - 1; i >= 0; i--) 
        num1.push_back(s1[i] - '0');
    for (int i = s2.length() - 1; i >= 0; i--) 
        num2.push_back(s2[i] - '0');
    
    vector<int> sum = addBigInt(num1, num2);
    for (int i = sum.size() - 1; i >= 0; i--) 
        cout << sum[i];
    return 0;
}

Big Integer Subtraction

Given two positive integers (without leading zeros), calculate their difference. The result may be negatvie.

Input Format
Two lines, each containing one integer.

Output Format
One line containing the difference.

Constraints
$1 \leq \text{integer length} \leq 10^5$

Example

Input:
32
11

Output:
21

Algorithm
First compare the magnitudes of the two numbers. If the first number is smaller, output a negative sign and compute the difference as $(second - first)$. Store digits in reverse order. During subtraction, maintain a borrow flag. For each position, subtract the corresponding digit of the smaller number and the borrow from the current digit of the larger number. If the result is negative, add 10 and set borrow to 1; otherwise set borrow to 0. Remove any leading zeros from the final result.

Implementation

#include <iostream>
#include <vector>
#include <string>
using namespace std;

bool greaterOrEqual(vector<int>& a, vector<int>& b) {
    if (a.size() != b.size()) return a.size() > b.size();
    for (int i = a.size() - 1; i >= 0; i--) {
        if (a[i] != b[i]) return a[i] > b[i];
    }
    return true;
}

vector<int> subtractBigInt(vector<int>& larger, vector<int>& smaller) {
    vector<int> diff;
    int borrow = 0;
    
    for (int i = 0; i < larger.size(); i++) {
        int digit = larger[i] - borrow;
        if (i < smaller.size()) digit -= smaller[i];
        
        if (digit < 0) {
            digit += 10;
            borrow = 1;
        } else {
            borrow = 0;
        }
        diff.push_back(digit);
    }
    
    while (diff.size() > 1 && diff.back() == 0) 
        diff.pop_back();
    return diff;
}

int main() {
    string s1, s2;
    cin >> s1 >> s2;
    vector<int> num1, num2;
    
    for (int i = s1.length() - 1; i >= 0; i--) 
        num1.push_back(s1[i] - '0');
    for (int i = s2.length() - 1; i >= 0; i--) 
        num2.push_back(s2[i] - '0');
    
    if (greaterOrEqual(num1, num2)) {
        vector<int> res = subtractBigInt(num1, num2);
        for (int i = res.size() - 1; i >= 0; i--) cout << res[i];
    } else {
        vector<int> res = subtractBigInt(num2, num1);
        cout << "-";
        for (int i = res.size() - 1; i >= 0; i--) cout << res[i];
    }
    return 0;
}

Big Integer Multiplication

Given a large non-negative integer $A$ (without leading zeros) and a smaller integer $B$, calculate $A \times B$.

Input Format
Two lines: the first contains integer $A$, the second contains integer $B$.

Output Format
One line containing the product.

Constraints
$1 \leq \text{length of } A \leq 100000$
$0 \leq B \leq 100000$

Example

Input:
2
3

Output:
6

Algorithm
This approach handles the case where one factor is a standard integer while the other is arbitrarily large. Process each digit of the large number from least to most significant, multiplying by the small integer and adding any carry from the previous step. Store $product % 10$ and carry forward $product / 10$. Continue processing while there are remaining digits or a non-zero carry.

Implementation

#include <iostream>
#include <vector>
#include <string>
using namespace std;

vector<int> multiplyBigInt(vector<int>& bigNum, int multiplier) {
    vector<int> product;
    long long carry = 0;
    
    for (int i = 0; i < bigNum.size() || carry; i++) {
        long long cur = carry;
        if (i < bigNum.size()) cur += 1LL * bigNum[i] * multiplier;
        product.push_back(cur % 10);
        carry = cur / 10;
    }
    
    while (product.size() > 1 && product.back() == 0) 
        product.pop_back();
    return product;
}

int main() {
    string s;
    int b;
    cin >> s >> b;
    vector<int> num;
    
    for (int i = s.length() - 1; i >= 0; i--) 
        num.push_back(s[i] - '0');
    
    if (b == 0) {
        cout << 0;
        return 0;
    }
    
    vector<int> res = multiplyBigInt(num, b);
    for (int i = res.size() - 1; i >= 0; i--) 
        cout << res[i];
    return 0;
}

Big Integer Division

Given a large non-negative integer $A$ (without leading zeros) and a positive integer $B$, calculate the quotient and remainder of $A / B$.

Input Format
Two lines: the first contains dividend $A$, the second contains divisor $B$.

Output Format
Two lines: the first contains the quotient, the second contains the remainder.

Constraints
$1 \leq \text{length of } A \leq 100000$
$1 \leq B \leq 10000$

Example

Input:
7
2

Output:
3
1

Algorithm
Process the dividend from most significant digit to least significant. Maintain a running remainder, initially 0. For each digit, update the remainder as $remainder \times 10 + current_digit$. Append $remainder / divisor$ to the quotient and update remainder to $remainder % divisor$. Since digits are processed from high to low but stored in reverse order, reverse the quotient before output and strip any leading zeros.

Implemantation

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

vector<int> divideBigInt(vector<int>& dividend, int divisor, int& remainder) {
    vector<int> quotient;
    remainder = 0;
    
    for (int i = dividend.size() - 1; i >= 0; i--) {
        remainder = remainder * 10 + dividend[i];
        quotient.push_back(remainder / divisor);
        remainder %= divisor;
    }
    
    reverse(quotient.begin(), quotient.end());
    while (quotient.size() > 1 && quotient.back() == 0) 
        quotient.pop_back();
    return quotient;
}

int main() {
    string s;
    int b, r;
    cin >> s >> b;
    vector<int> num;
    
    for (int i = s.length() - 1; i >= 0; i--) 
        num.push_back(s[i] - '0');
    
    vector<int> res = divideBigInt(num, b, r);
    for (int i = res.size() - 1; i >= 0; i--) 
        cout << res[i];
    cout << endl << r << endl;
    return 0;
}