3089282_ac_828ms_144k.c

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

#include <stdio.h>

int prime[90], num;
__int64 cnt;

void init()
{
	int i, j;

	prime[0] = 2;
	num = 1;
	for(i = 3; i <= 431; i+=2)
	{
		for(j = 3; j*j <= i; j+=2)
		{
			if(i%j==0)
			{
				goto l1;
			}
		}
		prime[num++] = i;
		l1:	;
	}
}

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

int main()
{
	int i, n, k;
	__int64 t;

	init();
	while(scanf("%d%d",&n,&k)==2)
	{
		if(k==0||k==n)
		{
			puts("1");
			continue;
		}
		cnt = 1;
		for(i = 0; prime[i] <= n&& i < num; i++)
		{
			t = calc(n,prime[i])-calc(n-k,prime[i])-calc(k,prime[i]);
			cnt *= (t+1);
		}
		printf("%I64d\n",cnt);
	}
	return 0;
}