3196529_wa.cpp

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

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

int num[80000], no[80000];
int cnt;
int prime[1000001];

int init(int n)
{
	int i, m, j;

	memset(prime,0,sizeof(prime));
	for(i = 3; i <= n; i+=2)
	{
		if(prime[i]==0)
		{
			for(j = i+i; j <= n; j += i)
			{
				prime[j] = 1;
			}
		}
	}
	m = 0;
	num[m++] = 2;
	for(i = 3; i <= n; i += 2)
	{
		if(prime[i]==0)
		{
			num[m++] = i;
		}
	}
	return m;
}

int calc(int n,int p)
{
	if(n < p)
		return 0;
	return n/p + calc(n/p,p);
}

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

int last(int a,int b)
{
	if(a==9)
		return b%2==0?1:9;
	return power(a,b%4)%10;
}

int main()
{
	int n, m, i, nn;
	int ans, n2, n5;

	scanf("%d%d",&n,&m);
	if(n==1||n==m||m==0)
	{
		puts("1");
		return 0;
	}
	cnt = init(n);
	for(i = 0; i < cnt; i++)
	{
		no[i] = calc(n,num[i])-calc(m,num[i])-calc(n-m,num[i]);
	}
	ans = 1;
	n2 = n5 = 0;
	for(i = 0; i < cnt; i++)
	{
		if(num[i]%10==1)
			continue;
		if(num[i]==2)
		{
			n2 = no[i];
			continue;
		}
		if(num[i]==5)
		{
			n5 = no[i];
			continue;
		}
		ans *= last(num[i]%10,no[i]);
	}
	nn = n2 < n5 ? n2 : n5;
	n2 -= nn;n5 -= nn;
	if(n5!=0)
	{
		puts("5");
	}
	else
	{
		if(n2!=0)
			ans *= power(2,(n2-1)%4+1)%10;
		printf("%d\n",ans%10);
	}
	return 0;
}