題目描述

給定正整數(shù)n, k，計(jì)算C(n, k)。答案保證在2^31以內(nèi)。

輸入

多組數(shù)據(jù)，每組數(shù)據(jù)僅一行，即2個(gè)整數(shù)n和k (n>=1) and k (0<=k<=n). 

以2個(gè)0結(jié)束輸入

輸出

對(duì)每個(gè)數(shù)據(jù)，輸出對(duì)應(yīng)的答案 

樣例輸入

Copy (如果復(fù)制到控制臺(tái)無(wú)換行，可以先粘貼到文本編輯器，再?gòu)?fù)制)

4 210 549 60 0
樣例輸出
625213983816
提示
#----------------------------------------------------------------------------------------------#這種題還需要說(shuō)嗎，大大的水資源啊，怎么能浪費(fèi)……思路什么的不說(shuō)什么了，先看第一次的代碼：
#include<cstdio>#define LL long long//雖然答案保證了在2^31內(nèi)，但我還是用了longlong，以防萬(wàn)一LL C(LL x,LL y){    LL sum=1;    for(int i=1;i<=y;i++)        sum=sum*(x--)/i;//邊乘邊除不會(huì)有問(wèn)題，因?yàn)槲覀冇?jì)算的時(shí)候乘是從大到小，除是從小到大，始終都能整除    return sum;}int main(){    LL a,b;    while(1)    {        scanf("%lld%lld",&a,&b);        if(!a&&!b) return 0;        if(a==b||b==0) {PRintf("1/n"); continue;}//覺(jué)得有可能超時(shí)，便加上了這句        printf("%lld/n",C(a,b));    }    return 0;}然后真的超時(shí)了………………【神尷尬】所以。。算法肯定不能怎么改了，但我們知道組合數(shù)有個(gè)重要的性質(zhì)（m>n）：于是，我們要加上這樣一行：
if(b>a-b) b=a-b;瞬間就1998ms變成了0ms……正確代碼：
#include<cstdio>#define LL long longLL C(LL x,LL y){    LL sum=1;    for(int i=1;i<=y;i++)        sum=sum*(x--)/i;    return sum;}int main(){    LL a,b;    while(1)    {        scanf("%lld%lld",&a,&b);        if(!a&&!b) return 0;        if(a==b||b==0) {printf("1/n"); continue;}        if(b>a-b) b=a-b;        printf("%lld/n",C(a,b));    }    return 0;}                                                                                                                                 By WZY