| 比赛 | 
    清华集训2017模板练习 | 
    评测结果 | 
    AAAAAAAAAA | 
    | 题目名称 | 
    超强的乘法问题 | 
    最终得分 | 
    100 | 
    | 用户昵称 | 
    栋霸霸 | 
    运行时间 | 
    1.941 s  | 
    | 代码语言 | 
    C++ | 
    内存使用 | 
    51.81 MiB  | 
    | 提交时间 | 
    2017-07-17 14:21:56 | 
显示代码纯文本
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
#include <vector>
#include <cmath>
#include <complex>
using namespace std;
const int N=1000000;
typedef complex<double> c;
c F[N],A[N],B[N];
char a[N],b[N];
int ans[N];
int rev(int x,int n)
{
	int ret=0;
	for(int i=0; (1<<i)<n; i++)ret=(ret<<1)|((x&(1<<i))>0);
	return ret;
}
void fft(c *a,int n,int f)
{
	for(int i=0; i<n; i++)F[rev(i,n)]=a[i];
	for(int i=2; i<=n; i*=2)
	{
		c wn=c(cos(2*acos(-1)*f/i),sin(2*acos(-1)*f/i));
		for(int j=0; j<n; j+=i)
		{
			c w=1;
			for(int k=j; k<j+i/2; k++)
			{
				c u=F[k],t=w*F[k+i/2];
				F[k]=u+t;
				F[k+i/2]=u-t;
				w*=wn;
			}
		}
	}
	for(int i=0; i<n; i++)a[i]=(F[i]/=(f==-1?n:1));
}
int main()
{
	freopen("bettermul.in","r",stdin);
	freopen("bettermul.out","w",stdout);
	scanf("%s%s",a,b);
	int l1=strlen(a),l2=strlen(b),n1=1,n2=1,n=1;
	while(n1<=l1)n1*=2;
	while(n2<=l2)n2*=2;
	while(n<2*max(n1,n2))n*=2;
	for(int i=0; i<n; i++)A[i]=(i<l1?a[l1-i-1]-'0':0);
	for(int i=0; i<n; i++)B[i]=(i<l2?b[l2-i-1]-'0':0);
	fft(A,n,1);
	fft(B,n,1);
	for(int i=0; i<n; i++)A[i]*=B[i];
	fft(A,n,-1);
	for(int i=0; i<n; i++)ans[i]=int(A[i].real()+0.5);
	for(int i=0; i<n-1; i++)ans[i+1]+=ans[i]/10,ans[i]%=10;
	bool f=0;
	for(int i=n-1; i>=0; i--)ans[i]?printf("%d",ans[i]),f=1:f||!i?printf("0"):0;
}