3196557_wa.cpp

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

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

int d[2][10];

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

int calc2(int n,int array[])
{
	if(n < 2)
		return 0;
	array[3] += getn(n,3);
	array[7] += getn(n,7);
	array[9] += getn(n,9);
	return n/2+calc2(n/2,array);
}

int calc5(int n)
{
	if(n < 5)
		return 0;
	return n/5+calc5(n/5);
}

int power(int a,int b)
{
	int ret = 1;
	
	while(b--)
	{
		ret *= a;
	}
	return ret;
}

int main()
{
	int n, m;
	int dd, d2, d3, d5;

	while(scanf("%d%d",&n,&m)==2)
	{
		m = n-m;
		if(n==m)
		{
			puts("1");
			continue;
		}
		memset(d,0,sizeof(d));
		d[0][2] = calc2(n,d[0]);
		d[1][2] = calc2(m,d[1]);
		d[0][5] = calc5(n);
		d[1][5] = calc5(m);
		d[0][2] -= d[1][2];d[0][3] -= d[1][3];
		d[0][5] -= d[1][5];d[0][7] -= d[1][7];
		d[0][9] -= d[1][9];
		d[0][3] += d[0][7]*3+d[0][9]*2;
		d2 = d[0][2];d3 = d[0][3];d5 = d[0][5];
		dd = d2 > d5 ? d5 : d2;
		d2 -= dd;d5 -= dd;
		if(d5!=0)
		{
			puts("5");
		}
		else
		{
			dd = power(3,d3%4)%10;
			if(d2!=0)
			{
				dd *= power(2,(d2-1)%4+1)%10;
			}
			printf("%d\n",dd%10);
		}
	}
	return 0;
}