代码链接：https://www.luogu.com.cn/record/122633958

代码：

#include<bits/stdc++.h>
using namespace std;
/*
# 【模板】A*B Problem 升级版（FFT 快速傅里叶变换）

## 题目背景

本题数据已加强，请使用 FFT/NTT，不要再交 Python 代码浪费评测资源。

## 题目描述

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

## 输入格式

第一行一个正整数，表示 $a$；  
第二行一个正整数，表示 $b$。

## 输出格式

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

## 样例 #1

### 样例输入 #1

83517934 327830610

### 样例输出 #1

27379735249159740

## 提示

【数据范围】   
$1\le a,b \le 10^{1000000}$

可能需要一定程度的常数优化。  
数据由 NaCly_Fish 重造
*/
const double pi=acos(-1);
char sa[1000001],sb[1000001];
int lena,lenb,lenc,limit=1,l=0,r[4000001],ans[2000001];
struct cp{
	double x,y;
	cp()
	{
		x=0;
		y=0;
	}
	cp(double _x,double _y)
	{
		x=_x;
		y=_y;
	}
};
cp operator+(cp a,cp b)
{
	return cp(a.x+b.x,a.y+b.y);
}
cp operator-(cp a,cp b)
{
	return cp(a.x-b.x,a.y-b.y);
}
cp operator*(cp a,cp b)
{
	return cp(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);
}
cp a[4000001],b[4000001],c[4000001],pw[2000001];
void fft(cp *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<<=1){
		cp wn(cos(pi/mid),type*sin(pi/mid)),w(1,0);
		pw[0]=w;
		for(int i=1;i<mid;++i) pw[i]=pw[i-1]*wn;
		for(int len=mid<<1,i=0;i<limit;i+=len){
			for(int j=0;j<mid;++j){
				cp x=a[i+j],y=pw[j]*a[i+j+mid];
				a[i+j]=x+y;
				a[i+j+mid]=x-y;
			}
		}
	}
	if(type==1) return;
	for(int i=0;i<=limit;++i) a[i].x/=limit;
}
int main()
{
	scanf("%s\n%s",sa,sb);
	lena=strlen(sa);
	lenb=strlen(sb);
	for(int i=0;i<lena;++i) a[i].x=sa[lena-i-1]-'0';
	for(int i=0;i<lenb;++i) b[i].x=sb[lenb-i-1]-'0';
	lenc=lena+lenb;
	while(limit<=lenc){
		limit<<=1;
		++l;
	}
	for(int i=0;i<limit;++i) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
	fft(a,1);
	fft(b,1);
	for(int i=0;i<=limit;++i) c[i]=a[i]*b[i];
	fft(c,-1);
	for(int i=0;i<lenc;++i) ans[i+1]=c[i].x+0.5;
	for(int i=1;i<=lenc;++i){
		ans[i+1]+=ans[i]/10;
		ans[i]%=10;
	}
	while(ans[lenc]==0&&lenc>1) --lenc;
	for(int i=lenc;i>=1;--i) printf("%d",ans[i]);
	return 0;
}