### Combinatoric selections题号：53 难度： 5 中英对照

There are exactly ten ways of selecting three from five, 12345:

123, 124, 125, 134, 135, 145, 234, 235, 245, and 345

In combinatorics, we use the notation, 5C3 = 10.

In general,

 nCr = n!r!(n−r)! ,where r ≤ n, n! = n×(n−1)×...×3×2×1, and 0! = 1.

It is not until n = 23, that a value exceeds one-million: 23C10 = 1144066.

How many, not necessarily distinct, values of nCr, for 1 ≤ n ≤ 100, are greater than one-million?

### Code


import java.math.BigInteger;

public final class p053 {

public static void main(String[] args) {
long start = System.nanoTime();
long result = run();
long end = System.nanoTime();
System.out.println(result);
System.out.println((end - start) / 1000000 + "ms");
}

public static long run() {
int result = 0;
BigInteger limit = BigInteger.TEN.pow(6);
int nlimit = 100;
for (int n = 1; n <= nlimit; n++) {
for (int r = 0; r <= n; r++) {
if ( binomial(n,r).compareTo(limit)>0 ) {
result++;
}
}
}
return result;
}

private static BigInteger factorial(int x) {
BigInteger y = BigInteger.ONE;
for (int i = 2; i <= x; i++) {
y = y.multiply(BigInteger.valueOf(i));
}
return y;
}

private static BigInteger binomial(int n, int r){
return factorial(n).divide(factorial(r).multiply(factorial(n - r)));
}
}

4075
151ms