Question

用分治法怎么写大整数乘法的算法（用c语言写)

Answer 1

//大数的乘法，以前写的
#include<iostream>
#include<string>
using namespace std;
void toInt(char *s,int *in)
{
	int i;
	strrev(s);
	for(i=0;i<strlen(s);i++)
	{
		in[i]=s[i]-'0';
	}
}
void revint(int *in,int n)
{
	int i,temp;
	for(i=0;i<n/2;i++)
	{
		temp=in[i];
		in[i]=in[n-i-1];
		in[n-i-1]=temp;
	}
}
int main()
{
	char c1[200],c2[200];
	int a1[200]={0};	//大数1
	int a2[200]={0};	//大数2
	int r2[300]={0};	//保存大结果
	int f=0;			//保存进位
	int i,j;
	cin>>c1>>c2;
	if(strcmp(c1,"0")!=0&&strcmp(c2,"0")!=0)
	{
	int len1=strlen(c1);
	int len2=strlen(c2);
	int maxlen=len1+len2;		//结果的最大位数
	toInt(c1,a1);
	toInt(c2,a2);
	for(j=0;j<len2;j++)
	{
		int r1[200]={0};	//保存小结果
		for(i=0;i<=len1;i++)
		{
			r1[i]=a2[j]*a1[i]+f;
			if(r1[i]>9)
			{
				f=r1[i]/10;
				r1[i]%=10;
			}
			else
			{
				f=0;
			}
		}
		for(i=0;i<=len1;i++)
		{
			r2[j+i]+=r1[i];
			if(r2[i+j]>9)
			{
				r2[i+j+1]+=r2[i+j]/10;
				r2[i+j]%=10;
			}
		}
		f=0;
	}
	revint(r2,maxlen);
	if(r2[0]!=0)
		cout<<r2[0];
	for(i=1;i<maxlen;i++)
	cout<<r2[i];
	}
	else
	cout<<"0";
	cout<<endl;
	return 0;
}

Answer 2

用FFT比较好

Answer 3

写出能跑的代码的话，需要现金酬劳和详细的要求。