大整数算法

#include <iostream>using namespace std;
const int N = 100010;int A[N], B[N], C[N];
int Add(int a[], int b[], int c[], int cnt) {
    int t = 0;//t表示进位
    for (int i=1; i<=cnt; i++) {        t += a[i] + b[i];//进位加上a和b第i位上的数        c[i] = t % 10;//c的值就是进位的个位数        t /= 10;//把t的个位数去掉只剩下十位数，即只剩下这个位置的进位    }    if (t) c[++cnt] = 1;//如果t==1，表示还有一个进位，要补上
    return cnt;}
int main() {
    string a, b;    cin >> a >> b;      //A和B倒着放进int数组，因为有进位，倒着放容易处理    int cnt1 = 0;    for (int i=a.size()-1; i>=0; i--)        A[++cnt1] = a[i] - '0';
    int cnt2 = 0;    for (int i=b.size()-1; i>=0; i--)        B[++cnt2] = b[i] - '0';
    int tot = Add(A, B, C, max(cnt1, cnt2));
    //因为A和B是倒着放的，所以C也要倒着输出    for (int i=tot; i>=1; i--)        cout << C[i];}

#include<iostream>#include<vector>using namespace std;//判断AB的大小 A>=Bbool cmp(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;}//C=A-Bvector<int> sub(vector<int>& a ,vector<int>& b){    vector<int> result;    int t=0;//进位    for(int i=0;i<a.size() || t;i++)    {        if(i<a.size()) t=a[i]-t;        if(i<b.size()) t-=b[i];        result.push_back((t+10)%10);        if(t<0) t=1;//如果t<0就进一位,否则不进        else t=0;    }    //清除前缀0      while(result.size()>1 && result.back()==0) result.pop_back();    return result;}

int main(){    string a,b;    vector<int> c,d,result;    cin>>a>>b;    for(int i=a.size()-1;i>=0;i--) c.push_back(a[i]-'0');    for(int i=b.size()-1;i>=0;i--) d.push_back(b[i]-'0');    if(cmp(c,d)) result=sub(c,d);    else printf("-"),result=sub(d,c);    for(int i=result.size()-1;i>=0;i--) cout<<result[i];    return 0;}

#include <iostream>#include <vector>
using namespace std;
vector <int> mul(vector <int> & A, int b) {    vector <int> C;
    int t = 0;    for (int i = 0; i < A.size(); i ++) {        t += A[i] * b;       // t + A[i] * b = 7218        C.push_back(t % 10); // 只取个位 8        t /= 10;             // 721 看作 进位    }
    while (t) {            // 处理最后剩余的 t        C.push_back(t % 10);        t /= 10;    }    //去掉前导0    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;}
int main() {    string a;    int b;    cin >> a >> b;
    vector <int> A;    for (int i = a.size() - 1; i >= 0; i --) A.push_back(a[i] - '0');
    auto C = mul(A, b);
    for (int i = C.size() - 1; i >= 0; i --) {        cout << C[i];    }
    return 0;}

#include <iostream>#include <vector>
using namespace std;
vector<int> mul(vector<int> &A, vector<int> &B) {    vector<int> C(A.size() + B.size(), 0); // 初始化为 0，且999*99最多 5 位
    for (int i = 0; i < A.size(); i++)        for (int j = 0; j < B.size(); j++)            C[i + j] += A[i] * B[j];
    int t = 0;    for (int i = 0; i < C.size(); i++) { // i = C.size() - 1时 t 一定小于 10        t += C[i];        C[i] = t % 10;        t /= 10;    }
    while (C.size() > 1 && C.back() == 0) C.pop_back(); // 必须要去前导 0，因为最高位很可能是 0    return C;}
int main() {    string a, b;    cin >> a >> b; // a = "1222323", b = "2323423423"
    vector<int> A, B;    for (int i = a.size() - 1; i >= 0; i--)        A.push_back(a[i] - '0');    for (int i = b.size() - 1; i >= 0; i--)        B.push_back(b[i] - '0');
    auto C = mul(A, B);
    for (int i = C.size() - 1; i >= 0; i--)        cout << C[i];
    return 0;}

#include<iostream>#include<vector>#include<algorithm>using namespace std;//int r=0;vector<int> div(vector<int> &A,int B,int &r){//r传入r的地址，便于直接对余数r进行修改    vector<int> C;    for(int i=0;i<A.size();i++){//对A从最高位开始处理        r=r*10+A[i];//将上次的余数*10在加上当前位的数字，便是该位需要除的被除数        C.push_back(r/B);//所得即为商在这一位的数字        r=r%B;    }    //由于在除法运算中，高位到低位运算，因此C的前导零都在vector的前面而不是尾部，vector只有删除最后一个数字pop_back是常数复杂度，而对于删除第一位没有相应的库函数可以使用，而且删除第一位，其余位也要前移，    //因此我们将C翻转，这样0就位于数组尾部，可以使用pop函数删除前导0    reverse(C.begin(),C.end());    while(C.size()>1&&C.back()==0) C.pop_back();    return C;}int main(){    string a;    int B,r=0; //代表余数    cin>>a>>B;    vector<int> A;    for(int i=0;i<a.size();i++) A.push_back(a[i]-'0');//注意这次的A是由高为传输至低位，由于在除法的手算过程中，发现从高位进行处理    //for(int i=0;i<A.size();i++) cout<<A[i];    //cout<<B;    auto C = div(A,B,r);    for(int i=C.size()-1;i>=0;i--) cout<<C[i];//将C从最高位传给最低位    cout<<endl<<r;//输出余数    cout<<endl;    return 0;}