Karatsuba乘法复杂度假了,求条
查看原帖
Karatsuba乘法复杂度假了,求条
886055
MoonCake2011楼主2024/5/11 13:12
#include<bits/stdc++.h>
using namespace std;
#define tj 10000
#define int long long
struct node{
	int a[250010];
	int len;
	node(int x=0){
		memset(a,0,sizeof a);
		for(len=1;x;len++)
			a[len]=x%tj,x/=tj;
		len--;
	}
	inline int &operator [] (int i){
		return a[i];
	}
	inline void fl(int l){
		len=l;
		for(int i=1;i<=len;i++)
			a[i+1]+=a[i]/tj,a[i]%=tj;
		for( ;!a[len] && len; )
			len--;
	}
};
void input(node &a){

	string s;cin>>s;
// 	for(int i=1;i<=1000;i++) s.push_back(rand()%11+'0');
	reverse(s.begin(),s.end());
	for(int i=0,w=1;i<s.size();i++,w*=10){
		if(i%4==0) w=1,a.len++;
		a[a.len]+=(s[i]-'0')*w;
	}
}
inline void print(node x){
	if(x.len==0){
		cout<<"0\n";
		return;
	}
	for(int i=max(1ll,x.len);i>=1;i--)
		if(x.len==i) printf("%d",x[i]);
		else printf("%04d",x[i]);
	cout<<"\n";
}
bool operator == (node x,node y){
	if(x.len!=y.len) return false;
    for(int i=x.len;i>=1;i--)
        if(x[i]!=y[i]) return false;
  	return true;
}
bool operator >= (node x,node y){
	if(x.len!=y.len) return x.len>y.len;
	for(int i=x.len;i>=1;i--)
		if(x[i]!=y[i]) return x[i]>y[i];
	return true;
}
node operator + (node x,node y){
	node c;
	c.len=max(x.len,y.len);
	for(int i=1;i<=c.len;i++)
		c[i]=x[i]+y[i];
	c.fl(c.len+2);
	return c;
}
node operator - (node x,node y){
	node c;
	int len=max(x.len,y.len);
	for(int i=1;i<=len;i++)
		c[i]=x[i]-y[i];
	for(int i=1;i<=len;i++)
		while(c[i]<0) c[i]+=tj,c[i+1]--;
	c.len=len;
	for( ;!c[c.len]; )
		c.len--;
	return c;
}
node operator * (node x,int y){
	node c;
	for(int i=1;i<=x.len;i++)
		c[i]=x[i]*y;
	c.fl(x.len+12);
	return c;
} 
node TIMES(node x,node y){
	node c(0);
	for(int i=1;i<=x.len;i++)
		for(int j=1;j<=y.len;j++)
			c[i+j-1]+=x[i]*y[j];
	c.fl(x.len+y.len+1);
	return c;
}
int tp[250010],tq[250010],cnt;
inline node operator * (node x,node y){//Karatsuba 乘法 
	cnt++;
	if(x.len==0 || y.len==0) return node(0);
	if(x.len<=100 || y.len<=100) return TIMES(x,y);
	if(x.len<y.len) swap(x,y);
	
	int mid=x.len>>1;
	node a(0),b(0),c(0),d(0);
	
	b.len=mid,a.len=x.len-mid;
	for(int i=1;i<=mid;i++) b[i]=x[i];
	for(int i=mid+1;i<=x.len;i++) a[i-mid]=x[i];
	a.fl(a.len),b.fl(b.len);
	if(y.len<mid) d=y;
	else{
		d.len=mid,c.len=y.len-mid;
		for(int i=1;i<=mid;i++) d[i]=y[i];
		for(int i=mid+1;i<=y.len;i++) c[i-mid]=y[i];
		c.fl(c.len),d.fl(d.len);
	}
	
	node ac=a*c,bd=b*d;
	node adbc=(a+b)*(c+d)-(ac+bd);
	
	for(int i=1;i<=ac.len;i++) tp[i]=ac[i];
	for(int i=1;i<=adbc.len;i++) tq[i]=adbc[i];
// 	memcpy(tp,ac.a,sizeof tp);
// 	memcpy(tq,adbc.a,sizeof tq);
	
	int len=ac.len;
	ac.len=0;
	for(int i=1;i<=mid*2;i++) ac[++ac.len]=0;
	for(int i=1;i<=len;i++) ac[++ac.len]=tp[i];
	
	len=adbc.len;
	adbc.len=0;
	for(int i=1;i<=mid;i++) adbc[++adbc.len]=0;
	for(int i=1;i<=len;i++) adbc[++adbc.len]=tq[i];
	return ac+adbc+bd;
} 
inline node operator / (node x,node y){
	node u,c;
	for(int i=x.len;i>=1;i--){
		u=u*tj+node(x[i]);
		while(u>=y){
			u=u-y;
			c[i]++;
		}
	}
	c.fl(x.len+1);
	return c;
}
inline node operator % (node x,node y){
	node u,c;
	for(int i=x.len;i>=1;i--){
		u=u*tj+node(x[i]);
		while(u>=y){
			u=u-y;
			c[i]++;
		}
	}
	return u;
}
node a,b;
signed main() {
//	ios::sync_with_stdio(0);
	input(a),input(b);
	print(a*b);
//	cout<<cnt*a.len<<"\n";
	return 0;
} 
2024/5/11 13:12
加载中...