蓝桥杯算法提高VIP-高精度乘法 （C++代码）（压位 17ms）

解题思路:

        压到极限的千万进制，也就是 7 位存一次。

        想起来我以前写的朴素乘法，惨不忍睹。

        当然还有比这更快的  快速傅里叶变换 （不会）。

        这里跟具体跟朴素算法也差不多，如果用 1w 进制，就是把每 4 位当作一个数存在一起，逆序放在一个数组里。这里用到 sscanf 把字符串变为数字，当然自己实现也不难。

参考代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
 
const int SIZE = 1000024;
LL A[SIZE >> 1], B[SIZE >> 1];
char cst[SIZE], cnd[SIZE];
 
int Conver(char ch[], LL N[]) {
    int Len = strlen(ch), Index = 0, Step = Len > 7 ? Len - 7 : 0;
    do {
        sscanf(ch + Step, "%7lld", &N[Index++]);
        Step -= 7;
    } while (Step >= 0);
    int C = Len % 7;
    if (C != 0 && Len > 7) {
        for (int pos = 0; pos < C; pos++)
            N[Index] = N[Index] * 10 + ch[pos] - 48;
        Index++;
    }
    return --Index;
}
 
int Multip(LL A[], int ALen, LL B[], int BLen) {
    LL tmp[SIZE >> 1];
    memcpy(tmp, A, (ALen + 1) * sizeof(LL));
    memset(A,   0, (ALen + 1) * sizeof(LL));
 
    for (int pst = 0; pst <= BLen; pst++)
        for (int pnd = 0; pnd <= ALen; pnd++)
            A[pnd + pst] += tmp[pnd] * B[pst];
 
    for (int pos = 0; pos <= ALen + BLen + 7; pos++) {
        if(A[pos] >= 10000000)
        A[pos + 1] += A[pos] / 10000000;
        A[pos] %= 10000000;
    }
 
    for (int pos = ALen + BLen + 7; pos >= 0; pos--)
        if (A[pos])
            return pos;
    return 0;
}
 
int main() {
    scanf("%s%s", &cst, &cnd);
    int ALen = Conver(cst, A);
    int BLen = Conver(cnd, B);
    int MLen = Multip(A, ALen, B, BLen);
 
    printf("%lld", A[MLen]);
    for (int pos = MLen - 1; pos >= 0; pos--)
        printf("%07lld", A[pos]);
}