大數運算

outline

• outline
• init
• 加法
• 減法
• 乘法
• 除法
• code
• mod

init

// 為了在比字典序時兩數的長度相同
void initial (string &a, string &b) {
    while (a.size() < b.size()) a = '0' + a;
    while (b.size() < a.size()) b = '0' + b;
}

bool findMax (string &a, string &b) {
    if (a < b) {
        swap (a, b);
        return true;
    }
    return 0;
}

bool del (string &a) {
    if (a[0] == '0') {
        a.erase (0, 1);
        return true;
    }
    else return false;
}

void DelAllZero (string &a) {
    while (del(a)) {
        del (a);
    }
}

加法

string add (string a, string b) {
    // 1024
    // [1, 0, 2, 4]
    initial (a, b);
    a = '0' + a; //補 0 避免進位溢位
    b = '0' + b;
    for (int i = a.size() - 1; i >= 0; i--) {
        int num1 = a[i] - '0';
        int num2 = b[i] - '0';
        if (num1 + num2 > 9) {
            a[i - 1] = a[i - 1] - '0' + 1 + '0';
            a[i] = (num1 + num2) - 10 + '0';
        }
        else a[i] = (num1 + num2) + '0';
    }

    del (a);
    return a;
}

減法

string sub (string a, string b) {
    initial (a, b);
    if (a == b) return "0";
    int fg = findMax (a, b);
    for (int i = a.size() - 1; i >= 0; i--) {
        int num1 = a[i] - '0';
        int num2 = b[i] - '0';
        if (num1 < num2) {
            a[i - 1] = a[i - 1] - '0' - 1 + '0';
            a[i] = (num1 - num2 + 10)  + '0';
        }
        else a[i] = (num1 - num2) + '0';
    }
    DelAllZero (a);
    if (fg) return "-" + a;
    return a;
}

乘法

string mul (string a, string b) {
    initial (a, b); 
    findMax (a, b);
    string res = "0";
    DelAllZero (b);
    // a = [1, 2, 3, 4, 5]
    // b = [0, 0, 5, 2, 4]
    // 12345 = 4 * 12345 + 2 * 123450 + 5 * 1234500
    for (int i = b.size() - 1; i >= 0; i--) {
        int num1 = b[i] - '0';
        if (i != b.size() - 1) a = a + '0';
        for (int i = 1; i <= num1; i++) {
            res = add (res, a);
        }
    }

    return res;
}

除法

• 550 / 24
  • 想成
    $550-24\times k$
  • 發現這樣效率太差
  • $550-240-240=70$
  • $550-24-24=22$

string div (string a, string b) {
    initial (a, b);
    if (a < b) return "0";
    DelAllZero (b);
    string res = "0"; // 除出來的答案
    string restmp = "1"; // 目前是10的幾次方算
    string tmp = b;// 減掉的 b*10^k
    for (int i = 1; i < (a.size() - b.size()); i++) {
        tmp += '0';
        restmp += '0';
    }
    initial (a, b); // 下一行比較 a >= b
    while (a >= b) {
        initial (a, tmp); // 為了下一行比較 a >= tmp
        if (a >= tmp) {
            a = sub (a, tmp);
            res = add (res, restmp);
        }
        else {
            tmp.erase (tmp.size() - 1);
            restmp.erase (restmp.size() - 1);
        }
        initial (a, b); // 為了等等要比較 a >= b
    }
    
    return res;
}

code

#include <bits/stdc++.h>
#define int long long

using namespace std;

void initial (string &a, string &b) {
    while (a.size() < b.size()) a = '0' + a;
    while (b.size() < a.size()) b = '0' + b;
}

bool findMax (string &a, string &b) {
    if (a < b) {
        swap (a, b);
        return true;
    }
    return false;
}

bool del (string &a) {
    if (a[0] == '0') {
        a.erase (0, 1);
        return true;
    }
    return false;
}

void DelAllZero (string &a) {
    while (del(a)) {
        del (a);
    }
}

string add (string a, string b) {
    initial (a, b);
    a = '0' + a;
    b = '0' + b;
    for (int i = a.size() - 1; i >= 0; i--) {
        int num1 = a[i] - '0';
        int num2 = b[i] - '0';
        if (num1 + num2 > 9) {
            a[i - 1] = a[i - 1] - '0' + 1 + '0';
            a[i] = (num1 + num2 - 10)  + '0';
        }
        else a[i] = (num1 + num2) + '0';
    }
    del (a);
    return a;
}

string sub (string a, string b) {
    initial (a, b);
    if (a == b) return "0";
    int fg = findMax (a, b);
    for (int i = a.size() - 1; i >= 0; i--) {
        int num1 = a[i] - '0';
        int num2 = b[i] - '0';
        if (num1 < num2) {
            a[i - 1] = a[i - 1] - '0' - 1 + '0';
            a[i] = (num1 - num2 + 10)  + '0';
        }
        else a[i] = (num1 - num2) + '0';
    }
    DelAllZero (a);
    if (fg) return "-" + a;
    return a;
}

string mul (string a, string b) {
    string res = "0";
    initial (a, b);
    findMax (a, b);
    DelAllZero (b);

    for (int i = b.size() - 1; i >= 0; i--) {
        int num1 = b[i] - '0';
        if (i != b.size() - 1) a = a + '0';
        for (int i = 0; i < num1; i++) {
            res = add (a, res);
        }
    }

    return res;
}

string div (string a, string b) {
    initial (a, b);
    if (a < b) return "0";
    DelAllZero (b);
    string res = "0";
    string restmp = "1";
    string tmp = b;
    for (int i = 0; i < (a.size() - b.size()); i++) {
        restmp += '0';
        tmp += '0';
    }

    initial (a, b);
    while (a >= b) {
        initial (a, tmp);
        if (a >= tmp) {
            a = sub (a, tmp);
            res = add (res, restmp);
        }
        else {
            restmp.erase (restmp.size() - 1);
            tmp.erase (tmp.size() - 1);
        }
        initial (a, b);
    }

    return res;
}

void run (string &op, string &a, string &b) {
    if (op == "/") cout << div (a, b) << "\n";
    if (op == "*") cout << mul (a, b) << "\n";
    if (op == "+") cout << add (a, b) << "\n";
    if (op == "-") cout << sub (a, b) << "\n";
}
 
signed main() {
    string a, b, op;
    cin >> a >> op >> b;
    run (op, a, b);
} 

mod

• 與題目 a021 無關

int mod(string a, int M) {
    int res = 0;

    for (int i = 0; i < a.length(); i++)
         res = (res * 10 + (int)a[i] - '0') % M;
 
    return res;
}

tags: 題解