UVa 10637 - Coprimes

// UVa 10637 - Coprimes

#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;

int n, m, mask[101], sol[31];

void comb(int i, int j, int l, int current_mask) {
	sol[i] = l;
	if (i == n) {
		if (m == j) {
			printf("%d", sol[1]);
			for (int k = 2; k <= i; k++)
				printf(" %d", sol[k]);
			printf("\n");
		}
		return;
	}
	for (int k = l; k <= m - j - l * (n - i - 1); k++) {
		if ((mask[k] & current_mask) == 0)
			comb(i + 1, j + k, k, current_mask | mask[k]);
	}
}

int main() {
	// sieve
	bool is_prime[101];
	vector<int> prime;
	memset(is_prime, true, sizeof(is_prime));
	prime.push_back(2);
	for (int j = 4; j <= 100; j += 2)
		is_prime[j] = false;
	for (int i = 3; i <= 100; i++)
		if (is_prime[i]) {
			prime.push_back(i);
			for (int j = i * i; j <= 100; j += (i << 1))
				is_prime[j] = false;
		}
	// calculate masks
	int one = 1;
	for (int k = 1; k <= 100; k++) {
		mask[k] = 0;
		for (int p = 0; p < prime.size(); p++) {
			if (k % prime[p] == 0)
				mask[k] = mask[k] | (one << p);
		}
	}
	// start
	int tt;
	scanf("%d", &tt);
	for (int t = 1; t <= tt; t++) {
		// input
		scanf("%d%d", &m, &n);
		printf("Case %d:\n", t);
		// combine
		comb(0, 0, 1, 0);
	}
	return 0;
}