UVA 369: Combinations

题目链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=5&problem=305&mosmsg=Submission+received+with+ID+8692218

题目大意:

GIVEN:

Compute the EXACT value of:

给你N和M求C。

解题思路：

      由于直接求出阶乘数据庞大，要用高精度算法。但是据题目说答案不超过32位，所以就用新的方法来做。把公式转化为

然后把m+1到n都存入数组，用（n-m）到1去和数组的数一起除以它们的最大公约数。最后把数组里面的数相乘起来就是答案。

解题代码：

#include<iostream>
using namespace std;
typedef long long ll;
ll s[105];
ll gcd(ll a,ll b){
	return a%b==0?b:gcd(b,a%b);
}
int main(){
	ll n,m;
	while(cin>>n>>m&&m+n){
		for(int i=1;i<=n;i++)
			s[i]=i;
		ll t=n-m,sum=1;
		if(t!=0){
			while(t!=1){
				for(int i=m+1,j=t;i<=n&&j!=1;i++){
					ll g=gcd(s[i],j);
					s[i]/=g;
					j/=g;
				}
				t--;
			}
			for(int i=m+1;i<=n;i++)
				sum*=s[i];
		}
		cout<<n<<" things taken "<<m<<" at a time is "<<sum<<" exactly."<<endl;
	}
        return 0;
}

扩展知识：http://en.wikipedia.org/wiki/Combinatorics

• 全局相关文章
• 相关文章