两个大整数除法及高精度取余

原理

• 遍历被除数

• 每次判断缓存rem是否大于除数s1

• 大于rem减去一次除数s1, 答案ans加一，再次判断

• 小于直接跳过，等于直接让rem为空，答案ans加一

• 退出循环后rem就是余数，处理一下ans前导0就可以得到商了

模拟了竖式除法，细节都在代码里都在代码里

代码演示1：粗糙版

#include <stdio.h>
#include <string.h>

char s1[1005], s2[1005]; // s1 / 22 = ans + rem;
int n1[1005], n2[1005], ans[1005], rem[1005]; //rem是余数（缓存） ,ans为商 

//大数减法 
void big_sub(int *a, const int *b) { //a >= b; a - b;
    for (int i = 1; i <= a[0]; i++) {
        a[i] -= b[i];
        if (a[i] < 0) {
            --a[i + 1]; //借一 
            a[i] += 10; 
        }
    }
    while (a[a[0]] == 0) --a[0];
    return ;
}

//判断大数a与b大数谁大 
int check(int *a, int *b) { //a大返回1，b大返回-1，相等返回0； 
    if (a[0] == b[0]) { //长度相等 
        for (int i = a[0]; i > 0; i--) {
            if (a[i] > b[i]) return 1;
            else if (a[i] < b[i]) return -1;
        }
        return 0;
    } else if (a[0] > b[0]) return 1;
    return -1;
}

int main() {
    // s1 / s2 

    scanf("%s", s2);    
    scanf("%s", s1);
    n1[0] = strlen(s1), n2[0] = strlen(s2);
    for (int i = 0, j = 1; j && s1[i]; i++, j++) { //正序存储 
        n1[j] = s1[i] - '0';
    }
    
    for (int i = 0, j = n2[0]; j && s2[i]; i++, j--) {  //倒序存储 
        n2[j] = s2[i] - '0';
    }
    // n1 / n2
    for (int i = 1; i <= n1[0]; i++) {
        
        //缓存后移 
        for (int j = rem[0]; j > 0; j--) {
            rem[j + 1] = rem[j];
        }
        ++rem[0], rem[1] = n1[i]; //头插法，保证高位在后面，低位在前 
        
        //输出rem看看 
    //    for (int k = 1; k <= rem[0]; k++) {
        //    printf("%d", rem[k]);
    //    } 
    //    printf("\n");
        
        if (check(rem, n2) == -1) continue;
        
        while (check(rem, n2) > 0) { //rem > n2
            ans[i]++; //ans全局初始化为0了 
            big_sub(rem, n2);
            //for (int w = rem[0]; w; w--) printf("%d", rem[w]);
        //    printf("\n");
        }
        if (check(rem, n2) == 0) ++ans[i], rem[0] = 0;
        
    }
    
    
    //输出商
    ans[0] = n1[0];
    int t = 1;
    while (ans[t] == 0 && t <= ans[0]) t++; //去除商的前导0 
    if (t > ans[0]) printf("0"); //特判，商为0时； 
    while (t <= ans[0]) printf("%d", ans[t++]); 
    printf("\n");
    
    
    //输出余数 
    if (rem[0] == 0) printf("0");
    for (int i = rem[0]; i; i--) printf("%d", rem[i]);
    printf("\n");
    
    return 0;
}

代码演示二：精简版

#include <stdio.h>
#include <string.h>

char s1[1005], s2[1005]; // s1 / 22 = ans + rem;
int n2[1005], ans[1005], rem[1005]; //rem是余数（缓存） ,ans为商 

//大数减法 
void big_sub(int *a, const int *b) { //a >= b; a - b;
    for (int i = 1; i <= a[0]; i++) {
        a[i] -= b[i];
        if (a[i] < 0) {
            --a[i + 1]; //借一 
            a[i] += 10; 
        }
    }
    while (a[a[0]] == 0) --a[0];
    return ;
}

//判断大数a与b大数谁大 
int check(int *a, int *b) { //a大返回1，b大返回-1，相等返回0； 
    if (a[0] == b[0]) { //长度相等 
        for (int i = a[0]; i > 0; i--) {
            if (a[i] > b[i]) return 1;
            else if (a[i] < b[i]) return -1;
        }
        return 0;
    } else if (a[0] > b[0]) return 1;
    return -1;
}

int main() {
    
    // s1 / s2 

    scanf("%s", s2);    
    scanf("%s", s1);
    n2[0] = strlen(s2);
    ans[0] = strlen(s1);
    
    for (int i = 0, j = n2[0]; j && s2[i]; i++, j--) {  //倒序存储 
        n2[j] = s2[i] - '0';
    }
    for (int i = 0; s1[i]; i++) { //遍历被除数
        
        //缓存后移 
        for (int j = rem[0]; j > 0; j--) {
            rem[j + 1] = rem[j];
        }
        ++rem[0], rem[1] = s1[i] - '0'; //头插法，保证高位在后面，低位在前 
        
        //输出rem看看 
    //    for (int k = 1; k <= rem[0]; k++) {
        //    printf("%d", rem[k]);
    //    } 
    //    printf("\n");
        
        if (check(rem, n2) == -1) continue;
        
        while (check(rem, n2) > 0) { //rem > n2
            ans[1 + i]++; //ans全局初始化为0了 
            big_sub(rem, n2);
            //for (int w = rem[0]; w; w--) printf("%d", rem[w]);
        //    printf("\n");
        }
        if (check(rem, n2) == 0) ++ans[1 + i], rem[0] = 0; //直接让rem为空
        
    }
    
    
    //输出商
    int t = 1;
    while (ans[t] == 0 && t <= ans[0]) t++; //去除商的前导0 
    if (t > ans[0]) printf("0"); //特判，商为0时； 
    while (t <= ans[0]) printf("%d", ans[t++]); 
    printf("\n");
    
    
    //输出余数 
    if (rem[0] == 0) printf("0");
    for (int i = rem[0]; i; i--) printf("%d", rem[i]);
    printf("\n");
    
    return 0;
}