SRM 500 - 1000pts.cpp

#include <map>
#include <set>

using namespace std;

class GeometricProgressions {
public:
  // decompose(120, &result) -> result will be {2:3, 3:1, 5:1}, meaning 2**3 * 3**1 * 5**1.
  void decompose(int n, map<int, int>* result) {
    // sqrt(500000000) < 22361
    for (int i = 2; n > 1 && i <= 22360; i++) {
      while (n % i == 0) {
	(*result)[i]++;
	n /= i;
      }
    }
  }

  // Add all of b * (q**i) where 0<=i<n into result.
  void add_results(int b, int q, int n, set<map<int, int> >* result) {
    map<int, int> p_q, p_b;
    if (b == 0 || q == 0) {
      p_q[0] = 0;
      result->insert(p_q);
    } else {
      decompose(q, &p_q);
      decompose(b, &p_b);
      for (int i = 0; i < n; i++) {
	result->insert(p_b);
	for (map<int, int>::iterator it = p_q.begin(); it != p_q.end(); it++) {
	  p_b[it->first] += it->second;
	}
      }
    }
  }

  int count(int b1, int q1, int n1, int b2, int q2, int n2) {
    set<map<int, int> > result;
    add_results(b1, q1, n1, &result);
    add_results(b2, q2, n2, &result);
    return result.size();
  }
};