SRM500 Div2 1000点問題 もうちょっと高速化しないときつそうだし答えちがう。/ http://community.topcoder.com/stat?c=problem_statement&pm=11343&rd=14429

GeometricProgressions.py

import math
import collections
class GeometricProgressions:
  def count(self, b1, q1, n1, b2, q2, n2):
    s = set()
    self.primes = self._primetable(int(math.ceil(math.sqrt(max(b1, q1, b2, q2)))))
    self._check01(b1, q1, n1, s)
    self._check01(b2, q2, n2, s)

    return len(s)

  def _check01(self, b, q, n, s):
    if b == 0:
      s.add((0))
      return

    if q == 0:
      # 0 and q
      s.add((0))
      bs = collections.Counter(self._prime_decomposition(b))
      self._add_set(bs, {}, n, s)

    if b == 1 and q == 1:
      s.add((1))
      return

    bs = collections.Counter(self._prime_decomposition(b))
    qs = collections.Counter(self._prime_decomposition(q))

    if b == 1:
      bs = {}
    if qs == 1:
      qs == {}

    self._add_set(bs, qs, n, s)

  def _add_set(self, b, q, n, s):
    for i in xrange(n):
      d = {}
      for k, v in b.items():
        d[k] = v
      for k, v in q.items():
        if d.has_key(k):
          d[k] += (v * i)
        else:
          d[k] = (v * i)
      s.add(tuple(d.items()))

  def _prime_decomposition(self, n):
    if n == 0:
      return None
    if n == 1:
      return None
    array = []
    for p in self.primes:
      while n % p == 0:
        n /= p
        array.append(p)
      if n == 1:
        break
      # p > n だったらbreak?
    else:
      array.append(n)

    return array

  def _primetable(self, max):
    sq = math.sqrt(max)
    table = []

    t = range(0, max+1)
    t[0] = 0
    t[1] = 0
    p = 2
    while p <= sq:
      if t[p] != 0:
        j = p + p
        while j <= max:
          t[j] = 0
          j += p
      p += 1
    for p in t:
      if p != 0:
        table.append(p)
    return table
    
# ----- test 4 -----
# abnormal error
# p0 = 32757
# p1 = 32662
# p2 = 267645
# p3 = 25547
# p4 = 6868
# p5 = 28254
# p6 = 55899
# all_right = KawigiEdit_RunTest(3, p0, p1, p2, p3, p4, p5, True, p6) and all_right
# # ------------------