1951277_ac_46ms_60k.cpp

北大大牛代码 1240道题的原代码 超级权威

# include <stdio.h>
# include <string.h>

__int64 power(int x, int y)
{
	int i;
	__int64 sum;

	sum = 1;
	for(i = 0; i < y; i++)
		sum *= x;
	return sum;
}

__int64 turn(int b, char tmp[])
{
	int i, len;
	__int64 sum;

	sum = 0;
	len = strlen(tmp);
	for(i = 0; i < len; i++)
    	sum += (int)(tmp[i]-'0')*power(b,len-i-1);
	return sum;
}
void strncopy(char *tmp, char p[], int len)
{
	int i;

	for(i = 0; i < len; i++)
		tmp[i] = p[i];
	tmp[len] = '\0';
}
__int64 devide(int b,char p[], char m[])
{
	int i, lenm, lenp;
	char tmp[10];
	__int64 r, tp, tm;

	i = lenm = strlen(m);
	lenp = strlen(p);
	strncopy(tmp,p,lenm);
	//puts(tmp);
	tp = turn(b,tmp);
	tm = turn(b,m);
	r = tm;
	//printf("tp = %I64d;tm = %I64d\n",tp,tm);
	while(1)
	{
		if(tp < tm)
		{
			while(tp < tm)
			{
				if(i >= lenp)
					goto finished;
				tp *= b;
				tp += (int)(p[i++]-'0');
			}
		}
		r = tp%tm;
		tp = r;
		//printf("r = %I64d\n",r);
	}
finished : ;
		   return tp;
}

int recover(int b, __int64 m, char *ans)
{
	int i;
	__int64 r;

	i = 0;
	while(m)
	{
		r = m % b;
		m /= b;
		ans[i++] = (char)r+'0';
	}
	return i;
}
int main()
{
	int b, i, j;
	__int64 r;
	char p[1001], m[10], ans[10];

	while(scanf("%d",&b)==1&&b)
	{
		scanf("%s%s",p,m);
		r = devide(b,p,m);
		if(b == 10||r == 0)
			printf("%I64d\n",r);
		else
		{
			j = recover(b,r,ans);
			for(i = j-1; i >= 0; i--)
				printf("%c",ans[i]);
			printf("\n");
		}
	}
	return 1;
}