c061 - 00530 - Binomial Showdown

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算二項式係數 C(N, M)，即從 N 個元素中選取 M 個元素的組合數。輸入為 N 和 M，輸出結果 C(N, M)。當 N=0 且 M=0 時，程式結束。

解題思路

計算二項式係數 C(N, M) 的標準公式為 C(N, M) = N! / (M! * (N-M)!)。然而，直接計算階乘可能會導致整數溢出。因此，程式採用了更有效率且避免溢出的方法。

程式的核心思想是簡化計算過程，避免直接計算大數的階乘。它利用了 C(N, M) = C(N, N-M) 的性質，選擇較小的數值進行計算，並在計算過程中不斷地進行簡化，即在每次乘法後，盡可能地除以公因數，以保持結果在可接受的範圍內。具體來說，程式計算從 (N-M+1) 到 N 的乘積，然後在每次乘法後，嘗試將結果除以 M，直到 M 變為 1 或結果無法再被 M 整除。

複雜度分析

• 時間複雜度: O(N-M)
• 空間複雜度: O(1)

程式碼

#include <iostream>
using namespace std;
long long int n,m;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	while(cin >> n >> m){
		if(n==0&&m==0)break;
		long long int nm=n-m,ans=1;
		if(nm<m){
			long long int tmp=nm;
			nm=m;
			m=tmp;
		}
		for(long long int i=nm+1;i<=n;++i){
			ans*=i;
			while(m>1&&ans%m==0){
				ans/=m;
				--m;
			}
		}
		cout << ans << "\n";
	}
}