排列组合计算

题目：有多少种方法可以从n个元素中不考虑顺序地选择k个元素？请编写一个程序来计算这个数字

思路：直接使用组合数公式

由于测试用例的case数据比较大，所以不能直接算阶乘，而是转换成r个分数相乘。由于每个分式可以约简，因此不会出现溢出的情况。

但是有一个坑点就是在OJ上提交显示超时，后来问了别人才知道，,因此当k>n/2时，可以化为.

最后的返回值要定义为long long 类型，否则会溢出

贴上最终AC的代码

#include<cstdio> 
typedef long long int64;

int n, r;
int64 get(){
	int64  ans = 1;
	int64 b = 1;
	if(r > n-r) r = n-r;
	for(int i = 1; i <= r; ++i){
		ans = ans * (n-r+i);
		b = b*i;
		if(ans % b == 0){
			ans = ans/b;
			b = 1;
		}

	}
	return ans/b;
} 

//分数约简
 
int main(){
	while(~scanf("%d %d", &n, &r)&&n){
		printf("%lld\n", get());
	}
	return 0;
}

转载自原文链接, 如需删除请联系管理员。

原文链接：排列组合计算，转载请注明来源！