3197458_ac_0ms_148k.cpp

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

#include <stdio.h>

int get(int n,int d)
{
	return n/10+(n%10>=d);
}

void calc(int t,int &n3,int &n7,int &n9)
{
	while(t >= 5)
	{
		t = ((t-5)/10+1)*2;
		n3 += get(t,3);
		n7 += get(t,7);
		n9 += get(t,9);
	}
}

void solve(int n,int &n2,int &n3,int &n5,int &n7,int &n9)
{
	int t;

	t = n;
	while(t >= 2)
	{
		n2 += t>>1;
		n3 += get(t,3);
		n7 += get(t,7);
		n9 += get(t,9);
		t >>= 1;
		calc(t,n3,n7,n9);
	}
	calc(n,n3,n7,n9);
	t = n;
	while(t >= 5)
	{
		n5 += t/5;
		t /= 5;
	}
}

int main()
{
	int n, m, t;
	int pow3[] = {1,3,9,7};
	int pow2[] = {2,4,8,6};
	int n2, m2, n3, m3, n5, m5, n7, m7, n9, m9;

	while(scanf("%d%d",&n,&m)==2)
	{
		m = n-m;
		n2 = n3 = n5 = n7 = n9 = 0;
		m2 = m3 = m5 = m7 = m9 = 0;
		solve(n,n2,n3,n5,n7,n9);
		solve(m,m2,m3,m5,m7,m9);
		n2 -= m2;n3 -= m3;n5 -= m5;n7 -= m7;n9 -= m9;
		t = n2 < n5 ? n2 : n5;
		n2 -= t;n5 -= t;
		n3 += n7*3+n9*2;
		if(n5!=0)
		{
			puts("5");
		}
		else
		{
			t = pow3[n3%4];
			if(n2!=0)
			{
				t *= pow2[(n2-1)%4];
			}
			printf("%d\n",t%10);
		}
	}
	return 0;
}