代码

#include<iostream>
#include<iomanip>
#ifndef BIGINT
#define BIGINT 1
#include<cstring>
#include<vector>
#ifndef FASTFTRANSFORM
#define FASTFTRANSFORM 1
#include<cmath>
#warning If GCC tells you "unused parameter 'a' [-Wunused-parameter]",it is NOT wrong.
#ifndef TYPES
#define TYPES 1
namespace Types{
	using ulong=unsigned long int;
	using size_t=unsigned int;
	using uint=unsigned int;
	using u8int=unsigned char;
	using u16int=unsigned short int;
	using u32int=unsigned long int;
	using u64int=unsigned long long int;
	using uint8=unsigned char;
	using uint16=unsigned short int;
	using uint32=unsigned long int;
	using uint64=unsigned long long int;
	using _8int=signed char;
	using _16int=signed short int;
	using _32int=signed long int;
	using _64int=signed long long int;
	using int8=signed char;
	using int16=signed short int;
	using int32=signed long int;
	using int64=signed long long int;
	using fshort=float;
	using fl=double;
	using fll=long double;
	using flong=long double;
	using f32=float;
	using f64=double;
	using f80=long double;
	using f128=long double;
	class complex{
		f64 a,b;
	public:
		constexpr complex(const complex& x):a(x.a),b(x.b){}
		constexpr complex():a(0),b(0){}
		constexpr complex(const f64& x,const f64& y):a(x),b(y){}
		constexpr complex(const f64& x):a(x),b(0){}
		constexpr complex operator=(const f64& x){return a=x;}
		constexpr complex operator=(const complex& x){
			a=x.a;b=x.b;
			return *this;
		}
		constexpr complex operator+(const complex& x)const{
			return complex(a+x.a,b+x.b);
		}
		constexpr complex operator-(const complex& x)const{
			return complex(a-x.a,b-x.b);
		}
		constexpr complex operator*(const complex& x)const{
			return complex(a*x.a-b*x.b,a*x.b+b*x.a);
		}
		constexpr complex operator+=(const complex& x){
			a+=x.a;
			b+=x.b;
			return *this;
		}
		constexpr complex operator-=(const complex& x){
			a-=x.a;
			b-=x.b;
			return *this;
		}
		constexpr complex operator*=(const complex& x){
			return (*this)=(*this)*x;
		}
		constexpr f64 real()const{return a;}
		constexpr f64 imag()const{return b;}
		constexpr f64 real(const double& x){return a=x;}
		constexpr f64 imag(const double& x){return b=x;}
	};
}
#endif
#ifndef CONSTANT
#define CONSTANT 1
namespace Constant{
	template<typename _Tp>
	_Tp max(const _Tp& a,const _Tp& b){
		return a<b?b:a;
	}
	template<typename First_Tp,typename... Rest_Tp>
	First_Tp max(const First_Tp& first,const Rest_Tp&...rest){
		return max(first,max(rest...));
	}
	template<typename _Tp>
	_Tp min(const _Tp& a,const _Tp& b){
		return a<b?a:b;
	}
	template<typename First_Tp,typename... Rest_Tp>
	First_Tp min(const First_Tp& first,const Rest_Tp&...rest){
		return min(first,min(rest...));
	}
#ifdef _GLIBCXX_CMATH
	constexpr double pi=acos(-1),pi2=2*pi,pi6=6*pi;
#else
	constexpr double pi=3.141'592'653'589'793'238'46
	,pi2=2*pi,pi6=6*pi;
#endif
}
#endif
namespace FFT{
	//Fast Fourier Transform
	template<const Types::size_t n>
	void dif(Types::complex a[]){
		constexpr Types::size_t half=n>>1,quarter=n>>2;
		Types::complex w(1,0),w3(1,0);
		const Types::complex wn(cos(Constant::pi2/n),sin(Constant::pi2/n)),wn3(cos(Constant::pi6/n),sin(Constant::pi6/n));
		for(Types::size_t i=0;i<quarter;i++){
			if(!(i&511))w=Types::complex(cos(Constant::pi2*i/n),sin(Constant::pi2*i/n)),w3=w*w*w;
			const Types::complex tmp1=a[i],tmp2=a[i+quarter],tmp3=a[i+half],tmp4=a[i+half+quarter];
			const Types::complex x=tmp1-tmp3;
			Types::complex y=tmp2-tmp4;
			y=Types::complex(y.imag(),-y.real());
			a[i]+=tmp3;
			a[i+quarter]+=tmp4;
			a[i+half]=(x-y)*w;
			a[i+half+quarter]=(x+y)*w3;
			w*=wn;
			w3*=wn3;
		}
		dif<half>(a);
		dif<quarter>(a+half);
		dif<quarter>(a+half+quarter);
	}
	template<>
	void dif<1>(Types::complex a[]){}
	template<>
	void dif<0>(Types::complex a[]){}
	template<>
	void dif<2>(Types::complex a[]){
		const Types::complex x=a[0],y=a[1];
		a[0]+=y;
		a[1]=x-y;
	}
	template<>
	void dif<4>(Types::complex a[]){
		const Types::complex tmp1=a[0],tmp2=a[1],tmp3=a[2],tmp4=a[3];
		const Types::complex x=tmp1-tmp3;
		Types::complex y=tmp2-tmp4;
		y=Types::complex(y.imag(),-y.real());
		a[0]+=tmp3;
		a[1]+=tmp4;
		a[2]=x-y;
		a[3]=x+y;
		dif<2>(a);
	}
	void rundif(Types::complex a[],const size_t& n){
		switch (n) {
			case 1<<1:dif<1<<1>(a);break;
			case 1<<2:dif<1<<2>(a);break;
			case 1<<3:dif<1<<3>(a);break;
			case 1<<4:dif<1<<4>(a);break;
			case 1<<5:dif<1<<5>(a);break;
			case 1<<6:dif<1<<6>(a);break;
			case 1<<7:dif<1<<7>(a);break;
			case 1<<8:dif<1<<8>(a);break;
			case 1<<9:dif<1<<9>(a);break;
			case 1<<10:dif<1<<10>(a);break;
			case 1<<11:dif<1<<11>(a);break;
			case 1<<12:dif<1<<12>(a);break;
			case 1<<13:dif<1<<13>(a);break;
			case 1<<14:dif<1<<14>(a);break;
			case 1<<15:dif<1<<15>(a);break;
			case 1<<16:dif<1<<16>(a);break;
			case 1<<17:dif<1<<17>(a);break;
			case 1<<18:dif<1<<18>(a);break;
			case 1<<19:dif<1<<19>(a);break;
			case 1<<20:dif<1<<20>(a);break;
			throw("Cannot support FFT for such a long sequence.");
		}
	}
	template<const Types::size_t n>
	void dit(Types::complex a[]){
		constexpr Types::size_t half=n>>1,quarter=n>>2;
		dit<half>(a);
		dit<quarter>(a+half);
		dit<quarter>(a+half+quarter);
		Types::complex w(1,0),w3(1,0);
		const Types::complex wn(cos(Constant::pi2/n),-sin(Constant::pi2/n)),wn3(cos(Constant::pi6/n),-sin(Constant::pi6/n));
		for(size_t i=0;i<quarter;i++){
			if(!(i&511))w=Types::complex(cos(Constant::pi2*i/n),-sin(Constant::pi2*i/n)),w3=w*w*w;
			const Types::complex tmp1=w*a[i+half],tmp2=w3*a[i+half+quarter];
			const Types::complex x=a[i],y=tmp1+tmp2;
			const Types::complex x1=a[i+quarter];
			Types::complex y1=tmp1-tmp2;
			y1=Types::complex(y1.imag(),-y1.real());
			a[i]+=y;
			a[i+quarter]+=y1;
			a[i+half]=x-y;
			a[i+half+quarter]=x1-y1;
			w*=wn;
			w3*=wn3;
		}
	}
	template<>
	void dit<1>(Types::complex a[]){}
	template<>
	void dit<0>(Types::complex a[]){}
	template<>
	void dit<2>(Types::complex a[]){
		const Types::complex x=a[0],y=a[1];
		a[0]+=y;
		a[1]=x-y;
	}
	template<>
	void dit<4>(Types::complex a[]){
		dit<2>(a);
		const Types::complex tmp1=a[2],tmp2=a[3];
		const Types::complex x=a[0],y=tmp1+tmp2;
		const Types::complex x1=a[1];
		Types::complex y1=tmp1-tmp2;
		y1=Types::complex(y1.imag(),-y1.real());
		a[0]+=y;
		a[1]+=y1;
		a[2]=x-y;
		a[3]=x1-y1;
	}
	void rundit(Types::complex a[],const Types::size_t& n){
		switch (n) {
			case 1<<1:dit<1<<1>(a);break;
			case 1<<2:dit<1<<2>(a);break;
			case 1<<3:dit<1<<3>(a);break;
			case 1<<4:dit<1<<4>(a);break;
			case 1<<5:dit<1<<5>(a);break;
			case 1<<6:dit<1<<6>(a);break;
			case 1<<7:dit<1<<7>(a);break;
			case 1<<8:dit<1<<8>(a);break;
			case 1<<9:dit<1<<9>(a);break;
			case 1<<10:dit<1<<10>(a);break;
			case 1<<11:dit<1<<11>(a);break;
			case 1<<12:dit<1<<12>(a);break;
			case 1<<13:dit<1<<13>(a);break;
			case 1<<14:dit<1<<14>(a);break;
			case 1<<15:dit<1<<15>(a);break;
			case 1<<16:dit<1<<16>(a);break;
			case 1<<17:dit<1<<17>(a);break;
			case 1<<18:dit<1<<18>(a);break;
			case 1<<19:dit<1<<19>(a);break;
			case 1<<20:dit<1<<20>(a);break;
			throw("Cannot support FFT for such a long sequence.");
		}
	}
}
#endif
namespace BigInt{
	//unsigned long long long int
	class ulllint;
	class ulllint{
#ifdef _GLIBCXX_IOMANIP
#ifdef _GLIBCXX_IOSTREAM
		friend std::istream;
		friend std::ostream;
#endif
#endif
		using ll=Types::_16int;
		static constexpr Types::size_t len=4;
		static constexpr ll base=10000;
		std::vector<ll>nums;
		std::vector<ll>::const_iterator begin()const{return nums.begin();}
		std::vector<ll>::const_iterator end()const{return nums.end();}
		Types::size_t size()const{return nums.size();}
		ll& operator[](const Types::size_t& x){return nums[x];}
		const ll& operator[](const Types::size_t& x)const{return nums[x];}
		ulllint(const std::vector<ll>::const_iterator& first,const std::vector<ll>::const_iterator& last)
		:nums(std::vector<ll>(first,last)){}// 用 vector 构造。
		ulllint(const Types::_16int& x,const ll& y){
			nums=std::vector<ll>(x,y);
		}// 用多个相同数构造，不处理进位。
		ulllint(const std::vector<ll>&x):nums(x){}
	public:
		//用整数构造
		ulllint(const Types::size_t& x=0){
			nums=std::vector<ll>(1,x);
			Types::size_t i=0;
			while(nums[i]>base)nums.push_back(nums[i]/base),nums[i++]%=base;
		}
		//复制
		ulllint(const ulllint& x):nums(x.nums){}
		ulllint& operator=(const ulllint& x){
			nums=x.nums;
			return *this;
		}
		static constexpr Types::size_t MAX_SIZE=1000000;
#ifdef _GLIBCXX_IOMANIP
#ifdef _GLIBCXX_IOSTREAM
		friend std::istream& operator>>(std::istream& cin,ulllint& x);
		friend std::ostream& operator<<(std::ostream& cout,const ulllint& x);
#endif
#endif
		friend ulllint operator+(const ulllint&,const ulllint&);
		friend ulllint operator-(const ulllint&,const ulllint&);
		friend ulllint operator*(const ulllint&,const ulllint&);
		friend ulllint operator*(const ulllint&,const Types::uint&);
		friend ulllint operator*(const ulllint&,const Types::u8int&);
		friend ulllint operator*(const ulllint&,const Types::u16int&);
		friend ulllint operator*(const ulllint&,const Types::u32int&);
		friend ulllint operator*(const ulllint&,const Types::size_t&);
		friend ulllint operator/(const ulllint&,const ulllint&);
		friend ulllint operator<<(const ulllint&,const Types::size_t&);
#if __cplusplus >= 202002L
		/*
		我相信编译器能做出比我更好的优化
		因此在支持的情况下，直接重载三路比较运算符
		*/
		friend auto operator<=>(const ulllint&,const ulllint&);
#else 
		friend Types::_8int __comp(const ulllint&,const ulllint&);
		friend bool operator<(const ulllint&,const ulllint&);
		friend bool operator>(const ulllint&,const ulllint&);
		friend bool operator<=(const ulllint&,const ulllint&);
		friend bool operator>=(const ulllint&,const ulllint&);
		/*
		C++ 20 之后，如果重载了 == 而未重载 !=
		则会将 a!=b 视为 !(a==b)，不需要单独重载
		*/
		friend bool operator!=(const ulllint&,const ulllint&);
#endif
		friend bool operator==(const ulllint&,const ulllint&);
		ulllint operator+=(const ulllint& x){
			if(x.size()>size()){
				nums.resize(x.size()+1);
			}
			for(Types::size_t i=0;i<size();i++){
				nums[i]+=x[i];
				nums[i+1]+=nums[i]/base;
				nums[i]%=base;
			}
			while((size()>1)&&nums[size()-1]==0)nums.pop_back();
			return *this;
		}
		ulllint operator-=(const ulllint& x){
			for(Types::size_t i=0;i<x.size();i++){
				if(nums[i]<x[i]){
					nums[i+1]--;
					nums[i]+=base;
				}
				nums[i]-=x[i];
			}
			while(size()>1&&nums[size()-1]==0)nums.pop_back();
			return *this;
		}
		friend ulllint operator*=(ulllint& x,const ulllint& y);
		ulllint operator<<=(const Types::size_t& x){
			nums.insert(begin(),x,0);
			return *this;
		}
	};
	char temp[ulllint::MAX_SIZE+1];
	//输入输出，采用 iostream
#ifdef _GLIBCXX_IOMANIP
#ifdef _GLIBCXX_IOSTREAM
	std::istream& operator>>(std::istream& cin,ulllint& x){
		std::cin>>temp;
		const size_t l=strlen(temp);
		size_t j=0;
		x.nums=std::vector<ulllint::ll>(l/ulllint::len+1);
		char *p=temp+l-1;
		char *const ed=temp+3;
		for(;p>=ed;p-=4){
			x[j]=(*p)+(*(p-1))*10+(*(p-2))*100+(*(p-3))*1000-53328;
			j++;
		}
		if(p>=temp)x[j]=std::stoi(std::string(temp,p+1));
		while(x.size()>1&&x[x.size()-1]==0)x.nums.pop_back();
		return cin;
	}
	std::ostream& operator<<(std::ostream& cout,const ulllint& x){
		if(x.size()==0)return cout;
		cout<<x[x.size()-1];
		for(Types::_32int i=((Types::_32int)x.size())-2;i>=0;i--){
			cout<<std::setfill('0')<<std::setw(ulllint::len)<<x[i];
		}
		return cout;
	}
#endif
#endif
	ulllint operator+(const ulllint& x,const ulllint& y){
		if(x.size()==0)return y;
		if(y.size()==0)return x;
		ulllint c(Constant::max(x.size(),y.size())+1,0);
		for(Types::size_t i=0;i<x.size();i++)c[i]+=x[i];
		for(Types::size_t i=0;i<y.size();i++)c[i]+=y[i];
		for(Types::size_t i=0;i<c.size()-1;i++)c[i+1]+=c[i]/ulllint::base,c[i]%=ulllint::base;
		while(c.size()>1&&c[c.size()-1]==0)c.nums.pop_back();
		return c;
	}
	ulllint operator-(const ulllint& x,const ulllint& y){
		if(y.size()==0)return x;
		ulllint z(x);
		for(Types::size_t i=0;i<y.size();i++){
			if(z[i]<y[i]){
				z[i]+=ulllint::base;
				z[i+1]--;
			}
			z[i]-=y[i];
		}
		while(z.size()>1&&z[z.size()-1]==0)z.nums.pop_back();
		return z;
	}
	ulllint operator*(const ulllint& x,const ulllint& y){
		static Types::complex tmp[1<<19];
		static ulllint c;
		Types::size_t n=x.size()+y.size()-1,s=1;
		while(s<=n)s<<=1;
		c.nums=std::vector<ulllint::ll>(s,0);
		for(Types::size_t i=Constant::max(x.size(),y.size());i<s;i++)tmp[i]=0; 
		for(Types::size_t i=0;i<x.size();i++)tmp[i].real(x[i]);
		for(Types::size_t i=0;i<y.size();i++)tmp[i].imag(y[i]);
		FFT::rundif(tmp,s);
		for(Types::size_t i=0;i<s;i++)tmp[i]*=tmp[i];
		FFT::rundit(tmp,s);
		const Types::_32int kkk=s;
		const Types::f64 change=0.5/kkk;
		Types::u64int _tmp=0;
		for(Types::size_t i=0;i<s;i++){
			_tmp+=(Types::u64int)((tmp[i].imag()*change)+0.5);
			c[i]=_tmp%ulllint::base;
			_tmp/=ulllint::base;
		}
		while(c.size()>1&&c[c.size()-1]==0)c.nums.pop_back();
		return c;
	}
	ulllint operator*(const ulllint& x,const Types::u16int& y){
		Types::u32int tmp=0;
		ulllint ans(x);
		for(Types::size_t i=0;i<x.size();i++){
			tmp+=ans[i]*y;
			ans[i]=tmp%ulllint::base;
			tmp/=ulllint::base;
		}
		while(tmp)ans.nums.push_back(tmp%ulllint::base),tmp/=ulllint::base;
		return ans;
	}
	ulllint operator*(const ulllint& x,const Types::u8int& y){
		Types::u32int tmp=0;
		ulllint ans(x);
		for(Types::size_t i=0;i<x.size();i++){
			tmp+=ans[i]*y;
			ans[i]=tmp%ulllint::base;
			tmp/=ulllint::base;
		}
		while(tmp)ans.nums.push_back(tmp%ulllint::base),tmp/=ulllint::base;
		return ans;
	}
	ulllint operator*(const ulllint& x,const Types::u32int& y){
		Types::u64int tmp=0;
		ulllint ans(x);
		for(Types::size_t i=0;i<x.size();i++){
			tmp+=ans[i]*y;
			ans[i]=tmp%ulllint::base;
			tmp/=ulllint::base;
		}
		while(tmp)ans.nums.push_back(tmp%ulllint::base),tmp/=ulllint::base;
		return ans;
	}
	ulllint operator<<(const ulllint& x,const Types::size_t& y){
		ulllint c(x);
		c.nums.insert(c.begin(),y,0);
		return c;
	}
	ulllint operator*=(ulllint& x,const ulllint& y){
		static Types::complex tmp[1<<19];
		Types::size_t n=x.size()+y.size()-1,s=1;
		while(s<=n)s<<=1;
		for(Types::size_t i=Constant::max(x.size(),y.size());i<s;i++)tmp[i]=0; 
		for(Types::size_t i=0;i<x.size();i++)tmp[i].real(x[i]);
		for(Types::size_t i=0;i<y.size();i++)tmp[i].imag(y[i]);
		FFT::rundif(tmp,s);
		for(Types::size_t i=0;i<s;i++)tmp[i]*=tmp[i];
		FFT::rundit(tmp,s);
		x.nums.resize(s);
		const Types::_32int kkk=s;
		const Types::f64 change=0.5/kkk;
		Types::u64int _tmp=0;
		for(Types::size_t i=0;i<s;i++){
			_tmp+=(Types::u64int)((tmp[i].imag()*change)+0.5);
			x[i]=_tmp%ulllint::base;
			_tmp/=ulllint::base;
		}
		while(x.size()>1&&x[x.size()-1]==0)x.nums.pop_back();
		return x;
	}
#if __cplusplus >= 202002L
	auto operator<=>(const ulllint& x,const ulllint& y){
		if(x.size()<y.size())return -1;
		if(x.size()>y.size())return 1;
		for(int i=x.size()-1;i>=0;i--){
			if(x[i]!=y[i])return x[i]-y[i];
		}
		return 0;
	}
	bool operator==(const ulllint& x,const ulllint& y){
		return (x<=>y)==0;
	}
#else
	Types::_8int __comp(const ulllint& x,const ulllint& y){
		if(x.size()<y.size())return -1;
		if(x.size()>y.size())return 1;
		for(int i=x.size()-1;i>=0;i--){
			if(x[i]!=y[i])return x[i]-y[i];
		}
		return 0;
	}
	bool operator<(const ulllint& x,const ulllint& y){return __comp(x,y)<0;}
	bool operator>(const ulllint& x,const ulllint& y){return __comp(x,y)>0;}
	bool operator<=(const ulllint& x,const ulllint& y){return __comp(x,y)<=0;}
	bool operator>=(const ulllint& x,const ulllint& y){return __comp(x,y)>=0;}
	bool operator==(const ulllint& x,const ulllint& y){return __comp(x,y)==0;}
	bool operator!=(const ulllint& x,const ulllint& y){return __comp(x,y)!=0;}
#endif
}
#endif
int main(){
	std::iostream::sync_with_stdio(0);
	BigInt::ulllint a,b;
	std::cin>>a>>b;
	std::cout<<a*b;
	return 0;
}

评测结果