1306.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define INF 30000
#define NMAX 100
int m[NMAX];
int k[NMAX];
int M,N;
void swap(int &a,int &b)
{
	int t;
	t=a;
	a=b;
	b=t;
}
int gcd(int a,int b)
{
	if(a<b)
		swap(a,b);
	while(b)
	{
		a=a%b;
		swap(a,b);
	}
	return a;
}
void solve()
{
	int i,j;
	for(i=1;i<=N;i++)
	{
		m[i]=i;
	}
	int a,b;
	int g;
	a=M;
	b=N-M;
	for(i=max(a,b);i>=1;i--)
	{
		m[i]=1;
	}
	for(i=1;i<=min(a,b);i++)
		k[i]=i;

	for(i=1;i<=min(a,b);i++)
	{
		for(j=max(a,b);j<=N;j++)
		{	
			g=gcd(m[j],k[i]);
			if(g>1)
			{
				m[j]/=g;
				k[i]/=g;
			}
			if(k[i]==1)
				break;
		}
	}
	int ans=1;
	for(i=1;i<=N;i++)
		ans*=m[i];
	printf("%d things taken %d at a time is %d exactly.\n",N,M,ans);


}
int main()
{

#if _DEBUG	
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
	while(1)
	{
		scanf("%d%d",&N,&M);
		if(!N)
			break;
		solve();
	}
	
#if _DEBUG
	fclose(stdin);
	fclose(stdout);
#endif
	return 1;
}