1000

GeometricProgressions2.py

import collections

class GeometricProgressions:
  def count(self, b1, q1, n1, b2, q2, n2):
    s = set()
    self._add_set(b1, q1, n1, s)
    self._add_set(b2, q2, n2, s)
    return len(s)

  def _add_set(self, b, q, n, s):
    b_primes = collections.Counter()
    q_primes = collections.Counter()
    if b == 0 or q == 0:
      s.add((0, 0))
      return

    self._prime_decomposition(b, b_primes)
    self._prime_decomposition(q, q_primes)
    for _ in xrange(n):
      s.add(tuple(b_primes.items()))
      for k, v in q_primes.items():
        b_primes[k] += v

  def _prime_decomposition(self, n, c):
    for i in xrange(2, 22361):
      while n % i == 0:
        c[i] += 1
        n /= i