比赛 东方幻想乡 S1 评测结果 AAAAAAAAAAAAAAAAAAAA
题目名称 西行寺幽幽子 最终得分 100
用户昵称 Truth.Cirno 运行时间 0.183 s
代码语言 C++ 内存使用 0.72 MiB
提交时间 2012-08-07 19:59:21
显示代码纯文本
#include <cstdio>
#include <cstring>
using namespace std;

struct bint
{
	int len,num[20001];
};

bool bcom(bint a,bint b)
{
	int i;
	if (a.len>b.len)
	{
		return(0);
	}
	else if (a.len<b.len)
	{
		return(1);
	}
	else
	{
		for (i=a.len-1;i>=0;i--)
			if (a.num[i]>b.num[i])
			{
				return(0);
			}
			else if (a.num[i]<b.num[i])
			{
				return(1);
			}
	}
	return(0);
}

bint bmin(bint a,bint b)
{
	int i;
	bool jie=0;
	for (i=0;i<a.len;i++)
	{
		a.num[i]=a.num[i]-b.num[i]-jie;
		if (a.num[i]<0)
		{
			a.num[i]+=10;
			jie=1;
		}
		else
			jie=0;
	}
	for (i=a.len-1;i>=0;i--)
		if (a.num[i]!=0)
		{
			a.len=i+1;
			break;
		}
	if (i==-1)
		a.len=0;
	return(a);
}

bint bdiv(bint a,bint b)
{
	bint c={0};
	int i,len;
	len=a.len-b.len;
	for (i=b.len-1;i>=0;i--)
		b.num[i+len]=b.num[i];
	for (i=0;i<len;i++)
		b.num[i]=0;
	b.len=a.len;
	while (len!=-1)
	{
		while (bcom(a,b)==0)
		{
			c.num[len]++;
			a=bmin(a,b);
		}
		b.len--;
		len--;
		if (len!=-1)
			for (i=len;i<b.len;i++)
				b.num[i]=b.num[i+1];
		b.num[b.len]=0;
	}
	for (i=20000;i>=0;i--)
		if (c.num[i]!=0)
		{
			c.len=i+1;
			break;
		}
	if (i==-1)
		c.len=0;
	return(c);
}

void bprint(bint a)
{
	if (a.len==0)
	{
		printf("0");
		return;
	}
	int i;
	for (i=a.len-1;i>=0;i--)
		printf("%d",a.num[i]);
}

int main(void)
{
	freopen("spring.in","r",stdin);
	freopen("spring.out","w",stdout);
	bint m={0},n={0},ans={0};
	int i;
	char str[20005];
	scanf("%s\n",&str);
	m.len=strlen(str);
	for (i=0;i<m.len;i++)
		m.num[i]=str[m.len-i-1]-'0';
	scanf("%s\n",&str);
	n.len=strlen(str);
	for (i=0;i<n.len;i++)
		n.num[i]=str[n.len-i-1]-'0';
	if (bcom(m,n)==0)
		ans=bdiv(m,n);
	bprint(ans);
	printf("\n");
	return(0);
}