高精度乘法II问题

解题思路：

本题能要求两个高精度数相乘。是可以用快速傅里叶变换来求的。

要想用快速傅里叶变换来求，就需要将题目转化成两个多项式相乘。

对于一个数 $A$ 我们可以看成 $a_{n-1}10^{n-1}+a_{n-2}10^{n-2}+…+a_010^0$，这就是一个多项式的形式了。

因此我们设 $A(x) = a_{n-1}x^{n-1}+a_{n-2}x^{n-2}+…+a_0x^0$，那么原数 $A$ 就是 $A(10)$。同理对于原数 $B$，我们也能设一个多项式 $B(x)$，也有 $B=B(10)$，那么本题所求的 $AB$ 就等于 $A(10)B(10)$，这就是一个多项式乘积的形式了，我们就可以用快速傅里叶变换来求了。我们能求出 $C(x)=A(x)B(x)$，那么本题的答案 $AB$ 就是 $C(10)$。求出 $C(x)$ 后，我们如何对应回一个数，就可以直接从低位到高位扫描一遍即可，第 $i$ 个系数就是第 $i$ 位，扫描的同时将进位往高位叠加即可。

C++ 代码

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

const int N = 300010;
const double PI = acos(-1);

struct Complex //复数
{
    double x, y; //x + yi
    Complex operator+(const Complex &t) const //复数加法
    {
        return {x + t.x, y + t.y};
    }
    Complex operator-(const Complex &t) const //复数减法
    {
        return {x - t.x, y - t.y};
    }
    Complex operator*(const Complex &t) const //复数乘法
    {
        return {x * t.x - y * t.y, x * t.y + y * t.x};
    }
}a[N], b[N]; //多项式

//rev[i] 表示 i 的二进制翻转后的数，bit 表示二进制最高位，tot 表示区间总长度
int rev[N], bit, tot;
char s1[N], s2[N]; //存储两个高精度数
int res[N]; //记录答案

//inv 为 1 时，系数表示法 -> 点表示法
//inv 为 -1 时，点表示法 -> 系数表示法
void fft(Complex a[], int inv) //快速傅里叶变换
{
    //求出最底层的序列顺序
    for(int i = 0; i < tot; i++)
        if(i < rev[i]) //只能交换一次，否则换过去换回来序列不变
            swap(a[i], a[rev[i]]);

    for(int mid = 1; mid < tot; mid *= 2) //枚举当前层每段区间的长度 mid，上一层的区间长度为 mid * 2
    {
        auto w1 = Complex({cos(PI / mid), inv * sin(PI / mid)});
        for(int i = 0; i < tot; i += mid * 2) //枚举上一层每段区间的左端点
        {
            auto wk = Complex({1, 0}); //k 从 0 开始，w0 为 (1, 0)
            for(int j = 0; j < mid; j++, wk = wk * w1) //枚举上一层区间中每一个数，并计算值
            {
                //A(wk) = A1(wk) - wk * A2(wk)
                auto x = a[i + j], y = wk * a[i + j + mid];
                a[i + j] = x + y, a[i + j + mid] = x - y;
            }
        }
    }
}

int main()
{
    scanf("%s%s", s1, s2);
    int n = strlen(s1) - 1, m = strlen(s2) - 1;
    for(int i = 0; i <= n; i++) a[i].x = s1[n - i] - '0';
    for(int i = 0; i <= m; i++) b[i].x = s2[m - i] - '0';

    //求 bit, tot, rev
    while((1 << bit) < n + m + 1) bit++;
    tot = 1 << bit;
    for(int i = 0; i < tot; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));

    fft(a, 1), fft(b, 1); //正向变换

    for(int i = 0; i < tot; i++) a[i] = a[i] * b[i]; //计算多项式的乘积

    fft(a, -1); //逆向变换

    //计算答案
    int k = 0; //记录答案的位数
    for(int i = 0, t = 0; i < tot || t; i++) //t 表示进位数
    {
        t += a[i].x / tot + 0.5; //0.5 用于四舍五入
        res[k++] = t % 10; //记录当前位的数
        t /= 10; //计算下一位的进位
    }

    while(k > 1 && !res[k - 1]) k--; //去除前导 0
    for(int i = k - 1; i >= 0; i--) printf("%d", res[i]); //输出答案

    return 0;
}