UVa 11889 - Benefit

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

vector<pair<int, int> > getPrimeFactorizationOf(int n) {
	vector<pair<int, int> > factors;
	pair<int, int> current_factor = pair<int, int>(2, 0);
	while (n % 2 == 0) {
		current_factor.second++;
		n /= 2;
	}
	if (current_factor.second > 0)
		factors.push_back(current_factor);

	for (int candidate = 3; candidate * candidate <= n && n > 1; candidate += 2) {
		int exponent = 0;
		while (n % candidate == 0) {
			exponent++;
			n /= candidate;
		}
		if (exponent > 0)
			factors.push_back(pair<int, int>(candidate, exponent));
	}

	if (n > 1)
		factors.push_back(pair<int, int>(n, 1));

	return factors;
}

int main() {
	int cases;
	for (scanf("%d\n", &cases); cases; cases--) {
		int a, c;
		scanf("%d %d", &a, &c);
		vector<pair<int, int> > a_factors = getPrimeFactorizationOf(a);
		vector<pair<int, int> > c_factors = getPrimeFactorizationOf(c);

		vector<pair<int, int> > b_factors;
		bool impossible = false;
		int i = 0, j = 0;
		while (i < a_factors.size() && j < c_factors.size() && !impossible) {
			int a_factor = a_factors[i].first;
			int c_factor = c_factors[j].first;
			if (a_factor == c_factor) {
				if (a_factors[i].second < c_factors[j].second)
					b_factors.push_back(pair<int, int>(c_factor, c_factors[j].second));
				i++;
				j++;
			} else if (a_factor > c_factor) {
				b_factors.push_back(pair<int, int>(c_factor, c_factors[j].second));
				j++;
			} else {
				impossible = true;
			}
		}
		if (i < a_factors.size())
			impossible = true;
		for (; j < c_factors.size(); j++)
			b_factors.push_back(pair<int, int>(c_factors[j].first, c_factors[j].second));

		if (impossible)
			printf("NO SOLUTION\n");
		else {
			int b = 1;
			for (int i = 0; i < b_factors.size(); i++) {
				for (int j = 0; j < b_factors[i].second; j++)
					b *= b_factors[i].first;
			}
			printf("%d\n", b);
		}

	}
	return 0;
}