euler53.c


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include <stdio.h>

/* number of r s.t. C(n, r)>x */
int nr_ncr_bigger(int n, int x)
{
	int prod = 1;
	int r = 0;

	while (prod <= x && r*2 < n) {
		r++;
		prod = prod * (n-r+1) / r;
	}

	if (prod <= x)
		return 0;
	else
		return n - r*2 + 1;
}

int main()
{
	int cnt = 0;
	for (int i = 1; i <= 100; i++)
		cnt += nr_ncr_bigger(i, 1000000);
	printf("%d\n", cnt);
}