e102 - Error

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算 C(b, c)，即從 b 個元素中選取 c 個元素的組合數。輸入 b 和 c，輸出組合數的值。

解題思路

題目要求計算組合數 C(b, c) = b! / (c! * (b-c)!)。由於直接計算階乘容易溢出，因此程式碼採用了更有效率的計算方式，避免了直接計算大數階乘。程式碼先計算 b * (b-1) * ... * (b-c+1)，然後再除以 (b-c) * (b-c-1) * ... * 1，這樣可以減少中間計算的數值範圍，降低溢出的風險。

複雜度分析

• 時間複雜度: O(c)
• 空間複雜度: O(1)

程式碼

#include <stdio.h>
int main(){
	int  b,c,b2;
	long long int ans;
	scanf("%d",&b);
	while (scanf("%d%d",&b,&c)>0){
		b2=b;
		for (ans=1;b>c;b--)
			ans*=b;
		for (;(b2-c)>0;c++)
			ans/=(b2-c);
		printf("%lld\n",ans);
	}
}