欧拉计划 Project Euler53（组合选择）题解
欧拉计划 Project Euler 53 题解
- 组合选择
- 问题：
- 思路
- code
- 答案
组合选择
从五个数中选择三个，恰好有十种方式，分别是：
( 5 3 ) = 10 \binom{5}{3}=10 (35)=10在组合数学中，我们记作： ( n r ) \binom{n}{r} (rn)
一般来说，组合数公式为： ( n r ) = n ! r ! ( n − r ) ! \binom{n}{r}=\frac{n!}{r!(n-r)!} (rn)=r!(n−r)!n!
其中：
- n n n：表示总数
- r r r：表示要选择的数目
- ( n r ) \binom{n}{r} (rn)：表示从 n n n 个数中选出 r r r 个数的组合数
- 且 0 ≤ r ≤ n 0\leq r\leq n 0≤r≤n
在 n = 23 n=23 n=23 时，首次出现超出一百万的组合数：
( 23 10 ) = 1144066 \binom{23}{10}=1144066 (1023)=1144066
问题：
对于 n ≤ 100 n\leq100 n≤100，有多少个不同形式的组合数 ( n r ) > 1 , 000 , 000 \binom{n}{r}>1{,}000{,}000 (rn)>1,000,000？
思路
两个for循环暴力求解即可，注意溢出问题的处理，具体看代码
code
// 4075
#include <bits/stdc++.h>using namespace std;using ll = long long;const int N = 1000000;ll C(int n, int k) {ll ans = 1;for (int i = 1; i <= k; ++i) {ans = ans * (n - i + 1) / i;if (ans > N) return ans; // 可能会溢出long long 若大于提前终止即可}return ans;
}bool check(int n, int k) {return C(n, k) > N;
}void solve() {ll ans = 0;for (int i = 1; i <= 100; ++i) {for (int j = 0; j <= i / 2; ++j) {if (check(i, j)) {if (j == i - j) ans++; // 中点else ans += 2;}}}cout << ans << "\n";}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int tt = 1; // cin >> tt;while (tt--) {solve();}return 0;
}
答案
4075 \boxed{4075} 4075