Problem53 100万を超えるnCr

問題

12345から3つ選ぶ選び方は10通りである.

123, 124, 125, 134, 135, 145, 234, 235, 245, 345
組み合わせでは, 以下の記法を用いてこのことを表す: 5C3 = 10

1 <= n <= 100について, 100万を超えるnCrは何通りか?

ソース

#include <Windows.h>
#include <math.h>
#include <stdio.h>

bool IsOver1000000(int NVal, int RVal)
{
    RVal = min(RVal, NVal-RVal);
    double ProdVal = 0;

    for (int I = NVal; I >= NVal - RVal + 1; I--) {
        ProdVal += log10((double)I);
    }
    for (int I = 2; I <= RVal; I++) {
        ProdVal -= log10((double)I);
    }
    return log10(1000000.0) < ProdVal;
}

void main()
{
    int cnt = 0;
    for(int N=1;N<=100;N++){
        for(int R=1;R<=100;R++){
            if (R <= N && IsOver1000000(N,R)){
                printf("%d個目は%dC%d\n",++cnt, N, R);
            }
        }
    }
}

実行結果

省略
4071個目は100C92
4072個目は100C93
4073個目は100C94
4074個目は100C95
4075個目は100C96

解説

対数を駆使してます。

MSDN --- log、logf、log10、log10f