Karatsuba 求调
查看原帖
Karatsuba 求调
760291
zhangbo1000楼主2024/2/23 07:55

rt,WA on #1,4,7,8。

code:

#include<vector>
#include<cstring>
#include<iostream>
#include<cmath>
using namespace std;
#define ll long long
#define int long long
#define base 100000000
ll n,lena,lenb;
vector<ll> add(const vector<ll>& a,const vector<ll>& b){
	vector<ll>c(max(a.size(),b.size())+1);
	n=max(a.size(),b.size()),lena= a.size(),lenb=b.size();
	for(int i=0;i<lena;i++)c[i]+=a[i];
	for(int i=0;i<lenb;i++)c[i]+=b[i];
	for(int i=0;i<n;i++){
		c[i+1]+=c[i]/base;
		c[i]%=base;
	}
	while(c.size()>1&&!c[c.size()-1])c.pop_back();
	return c;
}
vector<ll> jian(const vector<ll>& a,const vector<ll>& b){
	vector<ll>c(a);
	n=b.size();
	for(int i=0;i<n;i++){
		c[i]-=b[i];
		if(c[i]<0){
			c[i]+=base;
			c[i+1]--;
		}
	}
	while(c.size()>1&&!c[c.size()-1])c.pop_back();
	return c;
}
vector<ll> cheng(const vector<ll>& a,const vector<ll>& b){
	if(a.size()<65&&b.size()<65){
		vector<ll>c(a.size()+b.size()+1,0);
		ll n=c.size();
		int lena=a.size(),lenb=b.size();
		for(int i=0;i<lena;i++){
			for(int j=0;j<lenb;j++){
				c[(ll)i+j]+=a[i]*b[j];
			}
		}
		for(ll i=0;i<n;i++){
			c[i+1]+=c[i]/base;
			c[i]%=base;
		}
		while(c.size()>1&&!c[c.size()-1])c.pop_back();
		return c;
	}
	int len=max(a.size(),b.size())>>1;
	int lena=min(len,(int)a.size()),lenb=min(len,(int)b.size());
	vector<ll> A(a.begin()+lena,a.end()),B(a.begin(),a.begin()+lena);
	vector<ll> C(b.begin()+lenb,b.end()),D(b.begin(),b.begin()+lenb);
	vector<ll> AC(cheng(A,C)),BD(cheng(B,D));
	vector<ll> AD_BC(jian(jian(cheng(add(A,B),add(C,D)),AC),BD));
	vector<ll> x(len,0);
	AC.insert(AC.begin(),x.begin(),x.end());AC.insert(AC.begin(),x.begin(),x.end());
	AD_BC.insert(AD_BC.begin(),x.begin(),x.end());
	return add(add(AC,AD_BC),BD);
}
signed main(){
//	freopen("1.txt","r",stdin);
	string tmpa , tmpb;
	cin>>tmpa>>tmpb;
	vector<ll> a((tmpa.size()>>3)+1,0),b((tmpa.size()>>3)+1,0);
	int w=1,j=-1,lenaa=tmpa.length(),lenbb=tmpb.length();
	for(int i=0;i<lenaa;i++){
		if(!(i&7))j++,w=1;
		a[j]+=w*(tmpa[tmpa.length()-i-1]^'0');
		w*=10;
	}
	j=-1;
	for(int i=0;i<lenbb;i++){
		if(!(i&7))j++,w=1;
		b[j]+=w*(tmpb[tmpb.length()-i-1]^'0');
		w*=10;
	}
	vector<ll>ans;
	ans=cheng(a,b);
	cout<<ans[ans.size()-1];
	ll k=ans.size();
	k-=2;
	for(ll i=k;i>=0;i--){
		printf("%.8lld",ans[i]);
	}
	return 0;
}
2024/2/23 07:55
加载中...