UVa 369 - Combinations

// UVa 369 - Combinations

#include <iostream>

using namespace std;

long mult_list[100], div_list[100];

long gcd(long a, long b) {
	if (b > a)
		return gcd(b, a);
	else if (b == 0)
		return a;
	else
		return gcd(b, a % b);
}

int main() {
	int n, m;
	cin >> n >> m;
	while (n && m) {

		int mult_lower_bound, div_upper_bound;
		if (m < n - m) {
			mult_lower_bound = n - m + 1;
			div_upper_bound = m;
		} else {
			mult_lower_bound = m + 1;
			div_upper_bound = n - m;
		}

		int mult_list_count = 0, div_list_count = 0;
		for (int i = mult_lower_bound; i <= n; i++)
			mult_list[mult_list_count++] = i;
		for (int i = 2; i <= div_upper_bound; i++)
			div_list[div_list_count++] = i;

		for (int i = 0; i < mult_list_count; i++) {
			for (int j = 0; j < div_list_count; j++) {
				int g = gcd(mult_list[i], div_list[j]);
				mult_list[i] /= g;
				div_list[j] /= g;
			}
		}

		long sol = 1;
		for (int i = 0; i < mult_list_count; i++)
			sol *= mult_list[i];
		cout << n << " things taken " << m << " at a time is " << sol
				<< " exactly." << endl;

		cin >> n >> m;
	}
}