黄阿信的个人博客

本文所探讨的均为高精度数字对高精度数字进行的操作（除特殊说明外）、尚未讨论负数的情况、数字的最低位保存在数组下标0处、尚未进行压位操作（除特殊说明）

加法

关键代码：

for (int i = 0; i < len3; i++){
    ans[i] += num1[i] + num2[i];
    // 传递进位
    ans[i + 1] += ans[i] / 10;
    ans[i] %= 10;
}

练手题目：洛谷1601

AC代码:

/*
 * @Author      : YaleXin
 * @Email       : me@yalexin.top
 * @LastEditors : YaleXin
 */
#include <cstdio>
#include <cstring>
int num1[505] = {0}, num2[505] = {0}, ans[505] = {0};
int len1, len2, len3;
int main() {
    char buff[2001];
    scanf("%s", buff);
    len1 = strlen(buff);
    for (int i = 0; i < len1; i++) num1[i] = buff[len1 - i - 1] - '0';
    scanf("%s", buff);
    len2 = strlen(buff);
    for (int i = 0; i < len2; i++) num2[i] = buff[len2 - i - 1] - '0';
    len3 = len1 > len2 ? len1 : len2;
    for (int i = 0; i < len3; i++){
        ans[i] += num1[i] + num2[i];
        // 传递进位
        ans[i + 1] += ans[i] / 10;
        ans[i] %= 10;
    }
    if (ans[len3] != 0)len3++;
    for(int i = len3 - 1; i >= 0; i--)printf("%d", ans[i]);
    return 0;
}

减法

关键代码：

for(int i = 0; i < len1; i++){
    ans[i] += big[i] - sml[i];
    // 产生借位
    if (ans[i] < 0)ans[i + 1]--, ans[i] += 10;
}

练手题目：洛谷2142

AC代码：

/*
 * @Author      : YaleXin
 * @Email       : me@yalexin.top
 * @LastEditors : YaleXin
 */
#include <cstdio>
#include <cstring>
// 判断两个数字的大小关系
bool cmp(int len1, int len2, int num1[], int num2[]){
    if(len1 != len2)return len1 > len2;
    for(int i = len1 - 1; i >= 0; i--)
        if (num1[i] != num2[i])return num1[i] > num2[i];
    return true;
}
void sub(int big[], int len1, int sml[], int len2, bool positive){
    int ans[10090];
    memset(ans, 0, sizeof ans);
    for(int i = 0; i < len1; i++){
        ans[i] += big[i] - sml[i];
        if (ans[i] < 0)ans[i + 1]--, ans[i] += 10;
    }
    while (len1 >= 1 && ans[len1 - 1] == 0)len1--;
    if (len1 == 0){
        printf("0");
        return;
    }
    if (!positive) printf("-");
    for(int i = len1 - 1; i >= 0; i--)printf("%d", ans[i]);
}
int main() {
    int num1[10090], num2[10090];
    memset(num1, 0, sizeof num1);
    memset(num2, 0, sizeof num2);
    int len1, len2, len3;
    char buff[10090];
    scanf("%s", buff);
    len1 = strlen(buff);
    for (int i = 0; i < len1; i++) num1[i] = buff[len1 - i - 1] - '0';
    scanf("%s", buff);
    len2 = strlen(buff);
    for (int i = 0; i < len2; i++) num2[i] = buff[len2 - i - 1] - '0';
    if (cmp(len1, len2, num1, num2))sub(num1, len1, num2, len2, true);
    else sub(num2, len2, num1, len1, false);
    return 0;
}

乘法

关键代码：

for(int i = 0; i < len1; i++)
    for(int j = 0; j < len2; j++){
        // 相当于往左偏移
        ans[i + j] += num1[i] * num2[j];
        ans[i + j + 1] += ans[i + j] / 10;
        ans[i + j]  %= 10;
    }

练手题目：洛谷1303

AC代码:

/*
 * @Author      : YaleXin
 * @Email       : me@yalexin.top
 * @LastEditors : YaleXin
 */
#include <stdio.h>
#include <cstring>
int num1[2010] = {0}, num2[2010] = {0}, ans[4020] = {0};
int len1, len2, len3;
int main() {
    char buff[2001];
    scanf("%s", buff);
    len1 = strlen(buff);
    for(int i = 0; i < len1; i++)num1[i] = buff[len1 - i - 1] - '0';
    scanf("%s", buff);
    len2 = strlen(buff);
    for(int i = 0; i < len2; i++)num2[i] = buff[len2 - i - 1] - '0';
    for(int i = 0; i < len1; i++)
        for(int j = 0; j < len2; j++){
            ans[i + j] += num1[i] * num2[j];
            ans[i + j + 1] += ans[i + j] / 10;
            ans[i + j]  %= 10;
        }
    len3 = len1 + len2;
    while(ans[len3 - 1] == 0 && len3 >= 1)len3--;
    if (len3 == 0)return (printf("0"),0);
    for(int i = len3 - 1; i >= 0; i--)printf("%d", ans[i]);    
    return 0;
}

除法

高精度对高精度

emm，高精度除高精度的确写起来有点棘手，而且普通版本的时间复杂度达到了O(n^2)

原理还是模拟小学二年级的竖式除法

练习题目：一本通1308

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int cmp(int len1, int len2, int num1[], int num2[]){
    if(len1 != len2)return len1 - len2;
    for(int i = len1 - 1; i >= 0; i--)
        if (num1[i] != num2[i])return num1[i] - num2[i];
    return 0;
}
void sub(int big[], int &len1, int sml[], int len2){
    for(int i = 0; i < len1; i++){
        big[i] = big[i] - sml[i];
        if (big[i] < 0)big[i + 1]--, big[i] += 10;
    }
    while(len1 >= 1 && big[len1 - 1] == 0)len1--;
}
void numcpy(int src[], int len1, int dest[], int &len2, int startIndex){
    // 将 除数 扩展，即除数和被除数高位对齐
    for(int i = 0; i < len1; i++)dest[startIndex + i] = src[i];
    len2 = len1 + startIndex;
}
// a / b, 结束后a[] 中是余数，ans[]是商
void div(int a[], int len1, int b[], int len2, int ans[], int &len3){
    // temp用于扩展除数
    int temp[305], tempLen;
    len3 = len1 - len2 + 1;
    for(int i = len3 - 1; i >= 0; i--){
        memset(temp, 0, sizeof temp);
        numcpy(b, len2, temp, tempLen, i);
        while(cmp(len1, tempLen, a, temp) >= 0){
            ans[i]++;
            sub(a, len1, temp, tempLen);
        }
    }
}
void print(int ans[], int len1){
    while(len1 >= 1 && ans[len1 - 1] == 0)len1--;
    if (len1 == 0){
        printf("0\n");
    } else{
        for(int i = len1 - 1; i >= 0; i--)printf("%d", ans[i]);
        printf("\n");
    }
}
int main(){
    int num1[305], num2[305], ans[305], len1, len2, len3;
    char buff[305];
    scanf("%s", buff);
    len1 = strlen(buff);
    for (int i = 0; i < len1; i++) num1[i] = buff[len1 - i - 1] - '0';
    
    scanf("%s", buff);
    len2 = strlen(buff);
    for (int i = 0; i < len2; i++) num2[i] = buff[len2 - i - 1] - '0';
    
    memset(ans, 0, sizeof ans);
    div(num1, len1, num2, len2, ans, len3);

    print(ans, len3);
    print(num1, len2);
    return 0;
}

或者使用 Newton Division 方法，时间复杂度可以降到O(nlog(n))，emm，但是这个方法有点复杂，我不是很看得懂。

高精度对单精度

这个就简单多了，原理还是一样

关键代码：

for(int i = len - 1; i >= 0; i--){
    nowNum = nowNum * 10 + (long long)num[i];
    if (nowNum >= divNum){
        ans[i] = nowNum / divNum;
        nowNum = nowNum % divNum;
    }
}

练手题目：洛谷1480

AC代码：

#include<iostream>
#include<cstdio>
#include <cstring>
using namespace std;
int num[5005], len, ans[5005];
int main(){
    char buff[5005];
    scanf("%s", buff);
    len = strlen(buff);
    for(int i = 0; i < len; i++)num[i] = buff[len - i - 1] - '0';
    long long divNum;
    scanf("%lld", &divNum);
    long long nowNum = 0;
    for(int i = len - 1; i >= 0; i--){
        nowNum = nowNum * 10 + (long long)num[i];
        if (nowNum >= divNum){
            ans[i] = nowNum / divNum;
            nowNum = nowNum % divNum;
        }
    }
    while(len >= 1 && ans[len - 1] == 0)len--;
    if (len == 0)return printf("0"), 0;
    for(int i = len - 1; i >= 0; i--){
        printf("%d", ans[i]);
    }
    return 0;
}

求模

高精度对高精度

这个就没什么好讲的了，参考高精度对高精度除法即可

高精度对单精度

算法的原理是根据

(a + b) % c == (a % c + b % c) % c

因此高精度对单精度求模等价于从高位开始进行求模，然后将结果往低位传播即可

练手题目：poj2635

AC代码

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int MAX_NUM = 1e6;
bool notDeleted[MAX_NUM];
int prime[80000], total;
void getPrime(){
    for(int i = 2; i < MAX_NUM; i++){
        if (!notDeleted[i]){
            prime[total++] = i;
            for(int j = i * i; j > 0 && j < MAX_NUM; j += i)notDeleted[j] = true;
        }
    }
}
bool checkModZero(int num[], int len, int checkPrime){
    int mod = 0;
    for(int i = len - 1; i >= 0; i--)
        // 从高位求模，往后传播
        mod = (mod * 1000 + num[i]) % checkPrime;
    return mod == 0;
}
void handle(int num[], int &len, char buff[]){
    int size = strlen(buff), hand, ten, one;
    char tem;
    buff[size] = '\0', buff[size + 1] = '\0', buff[size + 2] = '\0';
    for(int i = 0; i < (size >> 1); i++){
        tem = buff[i];
        buff[i] = buff[size - i - 1];
        buff[size - i - 1] = tem;
    }
    for(len = 0; buff[len * 3] != '\0';len++){
        // 这里需要压位，否则会超时
        num[len] = 0;
        if (buff[len * 3 + 2] != '\0')num[len] = num[len] * 10 + buff[len * 3 + 2] - '0';
        if (buff[len * 3 + 1] != '\0')num[len] = num[len] * 10 + buff[len * 3 + 1] - '0';
        num[len] = num[len] * 10 + buff[len * 3] - '0';
    }
}
int main(){
    getPrime();
    char buff[105];
    int l, len, num[105];
    bool flag;
    while (~scanf("%s%d", buff, &l)){
        if (l == 0)break;
        flag = false;
        handle(num, len, buff);
        for(int i = 0; i < total && prime[i] < l; i++){
            if (checkModZero(num, len, prime[i])){
                printf("BAD %d\n", prime[i]);
                flag = true;
                break;
            }
        }
        if (!flag)printf("GOOD\n");
    }
    return 0;
}

高精度运算

加法

减法

乘法

除法

高精度对高精度

高精度对单精度

求模

高精度对高精度

高精度对单精度