题目描述
给定两个正整数 A 和 B,请你计算 A×B 的值。
输入格式
共两行,第一行包含整数 A,第二行包含整数 B。
输出格式
共一行,包含 A×B 的值。
数据范围
1≤A与B的长度≤10^5。
样例
输入样例:
2
3
输出样例:
6
算法1
思路 (暴力—Python) $O(1)$
直接上python的乘就好了
C++ 代码
a=int(input())
b=int(input())
print(a*b)
算法2
(FFT)
思路
例如数字:$$ A=a_{n-1}a_{n-2}…a_0$$
它的长为n,故此我们可以将A转化为
$$A=\sum_{i=0}^{n-1}a_{i} \times10^{i}$$
故此我们可以将它视为一个多项式:
$$A(x)=\sum_{i=0}^{n-1}a_{i} \times{x}^{i}$$ $$A=A(10)$$ $$C=A(10)\times B(10)$$
当然后面操作还要扫描一遍,为了让解决进位的问题。
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=3000010;
const double PI=acos(-1);
//定义复数并且完成运算符的定义
struct Complex{
double x,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};
}
Complex operator*(const Complex& t)const {
return {x*t.x-y*t.y,x*t.y+y*t.x};
}
}a[N],b[N];
char s1[N],s2[N];//输入的AB
int res[N];//答案
int rev[N],tot,bit;
//FFT模板
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){
auto w1=Complex({cos(PI/mid),inv*sin(PI/mid)});
for(int i=0;i<tot;i+=mid*2){
auto wk=Complex({1,0});
for(int j=0;j<mid;j++,wk=wk*w1){
auto x=a[i+j],y=wk*a[i+j+mid];
a[i+j]=x+y,a[i+j+mid]=x-y;
}
}
}
}
int main(){
cin>>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';
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+=a[i].x/tot+0.5;
res[k++]=t%10;
t/=10;
}
//去除高位0
while(k>1&&!res[k-1])k--;
for(int i=k-1;i>=0;i--)cout<<res[i];
}
您好,这里for(int i=0,t=0;i<tot||t;i++) 为什么是i < tot而不是i < n + m + 1
n+m+1是最正确的,不过多算一些也没问题。
差点误伤(