洛谷P1919 【模板】高精度乘法 | A*B Problem 升级版 题解

题目链接：P1919 【模板】高精度乘法 | A*B Problem 升级版

题意：

给你两个正整数 \(a,b\)，求 \(a \times b\)。

输入格式：

第一行一个正整数，表示 \(a\) 。

第二行一个正整数，表示 \(b\) 。

输出格式：

输出一行一个整数表示答案。

数据范围：

\(1\le a,b \le 10^{1000000}\)

注意到任意十进制整数都可以写成 \[ a_0\times 1 + a_1 \times 10^1 + a_2 \times 10^2 + \cdots + a_n\times 10^{n} \] 这就是一个 \(n\) 次多项式，不是么。

于是我们可以用 NTT 来优化这个计算，不会 NTT 的可以看这篇 快速数论变换 NTT

注意这本质上是个压位高精，不要忘记最后的进位哦。

时间复杂度 \(\mathcal{O}(n \log n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2097152 + 15))

const int P = 998244353;
const int G = 3, Gi = 332748118;
int a[N], b[N], c[N];
int l, r[N], limit = 1;
int qpow(int a, int b)
{
    int r = 1;
    while(b)
    {
        if(b & 1) r = r * a % P;
        b >>= 1; a = a * a % P;
    }
    return r;
}
void NTT(int *A, int type)
{
    for(int i = 0; i < limit; i++) if(i < r[i]) swap(A[i], A[r[i]]);
    for(int mid = 1; mid < limit; mid *= 2)
    {
        int Wn = qpow((type == 1 ? G : Gi), (P - 1) / (mid * 2));
        for(int j = 0; j < limit; j += (mid * 2))
        {
            int w = 1;
            for(int k = 0; k < mid; k++, w = (w * Wn) % P)
            {
                int x = A[j + k], y = w * A[j + k + mid] % P;
                A[j + k] = (x + y) % P; A[j + k + mid] = (x - y + P) % P;
            }
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    string x, y; cin >> x >> y; 
    int n = x.size() - 1, m = y.size() - 1;
    for(int i = 0; i <= n; i++) a[i] = (x[n - i] - '0'); // 本题这里可以不用模 P
    for(int i = 0; i <= m; i++) b[i] = (y[m - i] - '0');
    for(; limit <= n + m; l++, limit *= 2);
    for(int i = 0; i < limit; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
    NTT(a, 1); NTT(b, 1);
    for(int i = 0; i < limit; i++) a[i] = a[i] * b[i] % P;
    NTT(a, -1); int Inv = qpow(limit, P - 2);
    for(int i = 0; i < limit; i++) c[i] = a[i] * Inv % P;
    for(int i = 0; i < limit; i++)
        if(c[i] >= 10) { c[i + 1] += c[i] / 10, c[i] %= 10; }
    int o = limit; while(!c[o]) --o;
    for(int i = o; ~i; i--) cout << c[i];
    return 0;
}