你可能想找：[A*B Problem](https://www.luogu.com.cn/problem/P1303)
by Wangzj512 @ 2023-03-11 21:11:47
$1\le a,b \le 10^{1000000}$
等价于位数$\le 10^6$
$O(n^2)$会炸
请自行学习FFT等技术
by DJRicher @ 2023-03-11 21:15:52
看一下数据范围吧。
by UNNN @ 2023-03-12 16:22:09
```cpp
#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;
}
```
by skyc13 @ 2023-08-26 21:52:46