#include <iostream>
#include <cstdint> // uint64_t
/*
binomial_coefficient(n, k):
Computes "n choose k" using the multiplicative formula:
C(n, k) = product(i = 1..k) of (n - k + i) / i
Why this method?
- It avoids huge factorials (e.g., 37! is far too large for 64-bit)
- It keeps intermediate values small and exact
- It is efficient, clean, and idiomatic in C++
Returns:
The binomial coefficient as std::uint64_t.
*/
std::uint64_t binomial_coefficient(unsigned n, unsigned k) {
if (k > n) return 0;
// Use symmetry: C(n, k) == C(n, n-k)
if (k > n - k)
k = n - k;
std::uint64_t result = 1;
for (unsigned i = 1; i <= k; ++i) {
result = result * (n - k + i) / i;
}
return result;
}
int main() {
unsigned main_n = 37;
unsigned main_k = 6;
unsigned power_n = 7;
unsigned power_k = 1;
// Compute combinations
std::uint64_t main_combos = binomial_coefficient(main_n, main_k);
std::uint64_t power_combos = binomial_coefficient(power_n, power_k);
std::uint64_t total = main_combos * power_combos;
std::cout << "Main combinations (C(37,6)): " << main_combos << "\n";
std::cout << "Power combinations (C(7,1)): " << power_combos << "\n";
std::cout << "Total lottery combinations: " << total << "\n";
}
/*
run:
Main combinations (C(37,6)): 2324784
Power combinations (C(7,1)): 7
Total lottery combinations: 16273488
*/
