Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

万进制的大数乘法,附代码。

Posted by zycxy at 2011-09-25 14:04:15 on Problem 2389
#include <stdio.h>
#include <string.h>

int num1[10] = {0};
int num2[10] = {0};
int length1 = 0;
int length2 = 0;
char str1[41] = {0};
char str2[41] = {0};

int main()
{
	int i = 0, j = 0;
	int a[20] = {0};
	int b[20] = {0};
	int carry = 0;
	int result = 0;
	int length = 0;

	scanf("%s", str1);
	scanf("%s", str2);

	length1 = strlen(str1);
	length2 = strlen(str2);

	for(i = length1-1, j = 0; i >= length1%4; i -= 4, j++)
	{
		num1[j] = (str1[i]-48)+10*(str1[i-1]-48)+100*(str1[i-2]-48)+1000*(str1[i-3]-48);
	}
	carry = 1;
	for(; i >= 0; i--)
	{
		num1[j] += (str1[i]-48)*carry;
		carry *= 10;
	}
	if(length1%4)
	{
		length1 = length1/4+1;
	}
	else
	{
		length1 = length1/4;
	}

	for(i = length2-1, j = 0; i >= length2%4; i -= 4, j++)
	{
		num2[j] = (str2[i]-48)+10*(str2[i-1]-48)+100*(str2[i-2]-48)+1000*(str2[i-3]-48);
	}
	carry = 1;
	for(; i >= 0; i--)
	{
		num2[j] += (str2[i]-48)*carry;
		carry *= 10;
	}
	if(length2%4)
	{
		length2 = length2/4+1;
	}
	else
	{
		length2 = length2/4;
	}

	for(i = 0; i < length1; i++)
	{
		carry = 0;
		for(j = 0; j < i; j++)
		{
			b[j] = 0;
		}
		for(j = 0; j < length2; j++)
		{
			result = num1[i]*num2[j]+carry;
			b[j+i] = result%10000;
			carry = result/10000;
		}
		if(carry)
		{
			b[j+i] = carry;
		}
		for(length = 19; length >= 0; length--)
		{
			if(a[length] != 0 || b[length] != 0)
			{
				break;
			}
		}
		carry = 0;
		for(j = 0; j <= length; j++)
		{
			result = a[j]+b[j]+carry;
			a[j] = result%10000;
			carry = result/10000;
		}
		if(carry)
		{
			a[j] = carry;
		}
	}

	for(i = 19; i >= 0; i--)
	{
		if(a[i] != 0)
		{
			break;
		}
	}
	if(i < 0)
	{
		printf("0\n");
	}
	else
	{
		printf("%d", a[i--]);
		for(; i >= 0; i--)
		{
			printf("%d", a[i]/1000);
			a[i] %= 1000;
			printf("%d", a[i]/100);
			a[i] %= 100;
			printf("%d", a[i]/10);
			a[i] %= 10;
			printf("%d", a[i]);
		}
		printf("\n");
	}

	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator