• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

蓝桥杯 算法提高 高精度乘法

互联网 diligentman 2周前 (02-17) 7次浏览

蓝桥杯 算法提高 高精度乘法

问题描述
计算机真是最傻的东西;他都不能计算大于10^65-1的a*b,请你帮这个“最傻”的东西过关,否则它就真的只认识1和0了。

输入格式
共两行;
第一行输入一个整数a;
第一行输入一个整数b。

输出格式
共一行,一个表示a*b的整数。

数据规模和约定
1065-1<a,b<10201-1

代码如下:

#include<stdio.h>
#include<string.h>
void transition(char one[],int *a){
	for(int i=0;i<strlen(one);i++)
		a[i]=one[i]-48;
}
void f(int *sum1,int d){
	
	for(int i=d;i>0;i--)
		sum1[i]=sum1[i-1];
	sum1[0]=sum1[1]/10;
	sum1[1]=sum1[1]%10;
}
int calculate(int *sum1,int len1,int a[],int b){
	for(int i=len1-1;i>=0;i--){
		sum1[i]=a[i]*b+sum1[i];
		if(sum1[i]>9){
			if(i-1>=0){
				sum1[i-1]=sum1[i]/10;
				sum1[i]=sum1[i]%10;
			}				
		}
	}
	if(sum1[0]>9){
		f(sum1,len1);
		return len1+1;
	}
	else
		return len1;
}
int sum(int *sum1,int SL,int sum2[],int sl,int k){
	int i;
	for(i=0;i<k;i++)
		sum2[sl+i]=sum1[SL+i-k];
	for(i=0;i<SL-k;i++)
	{
		sum2[sl-1-i]=sum2[sl-1-i]+sum1[SL-1-k-i];
		if(sum2[sl-1-i]>9){
			if(sl-2-i>=0){
				sum2[sl-2-i]=sum2[sl-2-i]+sum2[sl-1-i]/10;
				sum2[sl-1-i]=sum2[sl-1-i]%10;
			}				
		}
	}
	for(i=0;i<sl+k;i++)
	{
		sum1[i]=sum2[i];
		sum2[i]=0;
	}
		
	if(sum1[sl-i-1]>9){
		f(sum1,sl+k);
		return sl+k+1;
	}
	else
		return sl+k;	
}
int main(){
	char one[1000],two[1000];
	int sum1[2002]={0},sum2[2002]={0},a[1000],b[1000],len1,len2,SL,sl;
	gets(one);
	gets(two);
	len1=strlen(one);
	len2=strlen(two);
	transition(one,a);
	transition(two,b);
	SL=calculate(sum1,len1,a,b[len2-1]);
	for(int i=2;i<=len2;i++){
		sl=calculate(sum2,len1,a,b[len2-i]);
		SL=sum(sum1,SL,sum2,sl,i-1);
	}
	for(int i=0;i<SL;i++)
		printf("%d",sum1[i]);
	return 0;
}


程序员灯塔
转载请注明原文链接:蓝桥杯 算法提高 高精度乘法
喜欢 (0)