【數論】計算組合數

問題 B(2713): [POJ2249]計算組合數

時間限制: 1 Sec  記憶體限制: 128 MB

題目描述

給定正整數n, k，計算C(n, k)。答案保證在2^31以内。

輸入

多組資料，每組資料僅一行，即2個整數n和k (n>=1) and k (0<=k<=n). 

以2個0結束輸入

輸出

對每個資料，輸出對應的答案 

樣例輸入

Copy (如果複制到控制台無換行，可以先粘貼到文本編輯器，再複制)

4 210 549 60 0      

樣例輸出

625213983816      

提示

#----------------------------------------------------------------------------------------------#

這種題還需要說嗎，大大的水資源啊，怎麼能浪費……

思路什麼的不說什麼了，先看第一次的代碼：

#include<cstdio>
#define LL long long//雖然答案保證了在2^31内，但我還是用了longlong，以防萬一
LL 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
"); continue;}//覺得有可能逾時，便加上了這句
        printf("%lld
",C(a,b));
    }
    return 0;
}      

然後真的逾時了………………【神尴尬】

是以。。算法肯定不能怎麼改了，但我們知道組合數有個重要的性質（m>n）：

于是，我們要加上這樣一行：

if(b>a-b) b=a-b;      

瞬間就1998ms變成了0ms……

正确代碼：

#include<cstdio>
#define LL long long
LL 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
"); continue;}
        if(b>a-b) b=a-b;
        printf("%lld
",C(a,b));
    }
    return 0;
}      

                                                                                                                                 By WZY