好恶心的算法

使用数组模拟计算

加法

1. 高精度数字利用字符串读入
2. 把字符串翻转存入两个整形数组 A，B
3. 从低位到高位，累加，进位，存余
4. 把数组 C 从高位到低位依次输出

const int N = 100005;
int A[N],B[N],C[N];
int la,lb,lc;

void add(int A[],int B[],int C[]){
    for(int i = 0; i <lc; i++){
        C[i] += A[i]+B[i];
        C[i+1] += C[i]/10;
        C[i] %= 10;
    }
    if(C[1c]) 1c++;
}

int main(){
    string a,b;
    cin >> a >> b;
    la = a.size();
    lb = b.size();
    lc = max(la,lb);
    for(int i = la-1; i>=0; i--){
        A[la-1-i] = a[i] -'0';
    }
    for(int i = lb-1; i>=0; i--){
        B[lb-1-i] = b[i] -'0';
    }
    add(A,B,C);
    for(int i = lc-1; i>=0; i--){
        cout << C[i];
    }
    return 0;
}

减法

1. 高精度数字利用字符串读入
2. 把字符串翻转存入两个整形数组 A，B
3. 若 A<B, 则交换 A,B, 输出负号
4. 从低位到高位，逐位求差，借位，存差。
5. 把数组 C 从高位到低位依次输出

const int N = 100005;
int A[N],B[N],C[N];
int la,lb,lc;

bool cmp(int A[], int B[]){
    if(la != lb) return la>lb;
    for(int i=la-1; i>=0; i--){
        if(A[i] != B[i]) return A[i]>B[i];
    }
    return true;
}

void sub(int A[], int B[], int C[]){
    for(int i = 0; i<lc; i++){
        if(A[i] < B[i]){
            A[i+1]--;
            A[i] += 10;
        }
        C[i] = A[i] - B[i];
    }
    while(lc && C[lc] == 0) lc--;
}

int main(){
    string a,b;
    cin >> a >> b;
    la = a.size();
    lb = b.size();
    lc = max(la, lb);
    for(int i = la-1; i >= 0; i--){
        A[la-1-i] = a[i]-'0';
    }
    for(int i = lb-1; i >= 0; i--){
        B[lb-1-i] = b[i]-'0';
    }
    if(!cmp(A,B)){
        swap(A,B);
    }
    sub(A,B,C);
    for(inr i = lc; i>=0; i--){
        cout<< C[i];
    }
    return 0;
}

乘法

1. 高精度数字利用字符串读入
2. 把字符串翻转存入两个整形数组 A，B
3. 从低位到高位，累加乘积，进位，存余
4. 把数组 C 从高位到低位依次输出

const int N = 100005;
int A[N],B[N],C[N];
int la,lb,lc;

void mul(int A[], int B[], int C[]){
    for(int i=0; i<la; i++){
        for(int j=0; j<lb; j++){
            C[i+j] += A[i]*B[i];
            C[i+j+1] += C[i+j]/10;
            C[i+j] %= 10;
        }
    }
    while(lc && C[lc]==0) lc--;
}

int main(){
    string a,b;
    cin >> a >> b;
    la = a.size();
    lb = b.size();
    lc = la+lb;
    for(int i = la-1; i >= 0; i--){
        A[la-1-i] = a[i]-'0';
    }
    for(int i = lb-1; i >= 0; i--){
        B[lb-1-i] = b[i]-'0';
    }
    mul(A,B,C);
    for(int i = lc; i>=0; i--){
        cout << C[i];
    }
    return 0;
}

除法

1. 高精度数字利用字符串读入
2. 把字符串翻转存入两个整形数组 A，B
3. 从高位到低位，当前被除数，存商，求余数。
4. 把数组 C 从高位到低位依次输出

const int N = 100005;
int A[N],B[N],C[N];
int la,lb,lc;

void div(int A[], int b, int C){
    long long r = 0;
    for(int i = la-1; i >= 0; i--){
        r = r*10 + A[i];
        C[la-i-1] = r/b;
        r %= b;
    }
    reverse(C, C+lc);
    while(lc && C[lc] == 0) lc--;
}

int main(){
    string a;
    cin >> a >> b;
    lc = la = a.size();
    for(int i = la-1; i >= 0; i--){
        A[la-i-1] = a[i] - '0';
    }
    div(A, b, C);
    for(int i = lc; i>=0; i--){
        cout << C[i];
    }
    return 0;
}