[Vijos P2000]A x B Problem

题目大意：叫你求A × B。

解题思路：高精度。你可千万别小看这道题，这是2017年7月27日的信息。

不过也不要怕，根据twd2的题解里写的，用普通的高精度加上一些小小的修改是可以过的。

那么直接上代码吧。

C++ Code：

#include<cstdio>

#include<cstring>

#include<cctype>

using namespace std;

char s[5005];

long long num1[701],num2[701],num3[1700];

int main(){

	int n;

	scanf("%d",&n);

	while(n--){

		memset(num1,0,sizeof(num1));

		memset(num2,0,sizeof(num2));

		int len=0;

		char c=getchar();

		while(!isdigit(c))c=getchar();

		while(isdigit(c)){

			s[++len]=c;

			c=getchar();

		}

		int w=1,l1=1,l2=1;

		for(int i=len;i;i--){

			if(w==100000000){

				w=1;l1++;

			}

			num1[l1]+=w*(s[i]-'0');

			w*=10;

		}

		len=0;

		while(!isdigit(c))c=getchar();

		while(isdigit(c)){

			s[++len]=c;

			c=getchar();

		}

		w=1;

		for(int i=len;i;i--){

			if(w==100000000){

				w=1;l2++;

			}

			num2[l2]+=w*(s[i]-'0');

			w*=10;

		}

		memset(num3,0,sizeof(num3));

		int l3=l1+l2+4;

		for(int i=1;i<=l1;i++)

		for(int j=1;j<=l2;j++)num3[i+j-1]+=num1[i]*num2[j];

		for(int i=1;i<=l1+l2+3;i++)

		if(num3[i]>=100000000){

			num3[i+1]+=num3[i]/100000000;

			num3[i]%=100000000;

		}

		while(num3[l3]==0&&l3>1)l3--;

		printf("%lld",num3[l3]);

		for(int i=l3-1;i;i--)printf("%08lld",num3[i]);

		puts("");

	}

	return 0;

}

这是时间使用情况：

我觉得时间用的并不是很多，就把乘法和除法、取模放在一块，结果居然被我卡过去了！！

C++ Code：

#include<cstdio>

#include<cstring>

#include<cctype>

using namespace std;

char s[5005];

long long num1[701],num2[701],num3[1700];

int main(){

	int n;

	scanf("%d",&n);

	while(n--){

		memset(num1,0,sizeof(num1));

		memset(num2,0,sizeof(num2));

		int len=0;

		char c=getchar();

		while(!isdigit(c))c=getchar();

		while(isdigit(c)){

			s[++len]=c;

			c=getchar();

		}

		int w=1,l1=1,l2=1;

		for(int i=len;i;i--){

			if(w==100000000){

				w=1;l1++;

			}

			num1[l1]+=w*(s[i]-'0');

			w*=10;

		}

		len=0;

		while(!isdigit(c))c=getchar();

		while(isdigit(c)){

			s[++len]=c;

			c=getchar();

		}

		w=1;

		for(int i=len;i;i--){

			if(w==100000000){

				w=1;l2++;

			}

			num2[l2]+=w*(s[i]-'0');

			w*=10;

		}

		memset(num3,0,sizeof(num3));

		int l3=l1+l2+4;

		for(int i=1;i<=l1;i++)

		for(int j=1;j<=l2;j++){

			num3[i+j-1]+=num1[i]*num2[j];

			num3[i+j]+=num3[i+j-1]/100000000;

			num3[i+j-1]%=100000000;

		}

		while(num3[l3]==0&&l3>1)l3--;

		printf("%lld",num3[l3]);

		for(int i=l3-1;i;i--)printf("%08lld",num3[i]);

		puts("");

	}

	return 0;

}

这是时间使用情况，可以发现，除了第一个点，其他都是900+ms的，有一个甚至达到了996ms！！这说明我RP好23333333。

巴特西

[Vijos P2000]A x B Problem

最新文章

热门文章