给定两个正整数 \(A\) 和 \(B\),请你计算 \(A \times B\) 的值。
共两行,第一行包含整数 \(A\),第二行包含整数 \(B\)。
共一行,包含 \(A \times B\) 的值。
\(1 \le A与B的长度 \le 10^5\)。
2 3
6
fft
设 \(A\) 由高位到低位的值分别为 \(a_0,a_1,\dots,a_{n-1}\),构造一个 \(n-1\) 次多项式 \(f(x)=a_0+a_1x+a_2x^2+\dots +a_{n-1}x^{n-1}\),同理由 \(B\) 构造的多项式 \(g(x)=b_0+b_1x+b_2x^2+\dots +b_{m-1}x^{m-1}\),而 \(A=f(10),B=g(10)\),要求 \(A\times B=f(10)\times g(10)\),而 \(fft\) 可求得 \(h(x)=f(x)\times g(x)\),最后即求 \(h(10)\)。注意求解的 \(h(x)\) 的系数并不是最后的答案,其系数也可能不是一位数
// Problem: 高精度乘法II // Contest: AcWing // URL: https://www.acwing.com/problem/content/3126/ // Memory Limit: 64 MB // Time Limit: 1000 ms // // Powered by CP Editor (https://cpeditor.org) // %%%Skyqwq #include <bits/stdc++.h> //#define int long long #define help {cin.tie(NULL); cout.tie(NULL);} #define pb push_back #define fi first #define se second #define mkp make_pair using namespace std; typedef long long LL; typedef pair<int, int> PII; typedef pair<LL, LL> PLL; template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; } template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; } template <typename T> void inline read(T &x) { int f = 1; x = 0; char s = getchar(); while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); } while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar(); x *= f; } const int N=3e5+5; const double pi=acos(-1); int n,m,bit,tot,rev[N],res[N]; char A[N],B[N]; struct cp { double x,y; cp operator+(const cp &o)const { return {x+o.x,y+o.y}; } cp operator-(const cp &o)const { return {x-o.x,y-o.y}; } cp operator*(const cp &o)const { return {x*o.x-y*o.y,x*o.y+y*o.x}; } }a[N],b[N]; void fft(cp 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<<=1) { cp w1={cos(pi/mid),inv*sin(pi/mid)}; for(int i=0;i<tot;i+=mid<<1) { cp wk={1,0}; for(int j=0;j<mid;j++,wk=wk*w1) { cp x=a[i+j],y=a[i+j+mid]; a[i+j]=x+wk*y,a[i+j+mid]=x-wk*y; } } } } int main() { help; cin>>A>>B; n=strlen(A),m=strlen(B); n--,m--; for(int i=0;i<=n;i++)a[i].x=A[n-i]-'0'; for(int i=0;i<=m;i++)b[i].x=B[m-i]-'0'; 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 t=0,k=0; for(int i=0;i<tot||t;i++) { t+=a[i].x/tot+0.5; res[k++]=t%10; t/=10; } while(k>1&&!res[k-1])k--; for(int i=k-1;~i;i--)cout<<res[i]; return 0; }