Problem:


Problem A: Everlasting...?

Everlasting Sa-Ga, a new, hot and very popular role-playing game, is out on October 19, 2008.
Fans have been looking forward to a new title of Everlasting Sa-Ga.

Little Jimmy is in trouble. He is a seven-year-old boy, and he obtained the Everlasting Sa-Ga
and is attempting to reach the end of the game before his friends. However, he is facing difficulty
solving the riddle of the first maze in this game -- Everlasting Sa-Ga is notorious in extremely
hard riddles like Neverending Fantasy and Forever Quest.

The riddle is as follows. There are two doors on the last floor of the maze: the door to the
treasure repository and the gate to the hell. If he wrongly opens the door to the hell, the game
is over and his save data will be deleted. Therefore, he should never open the wrong door.

So now, how can he find the door to the next stage? There is a positive integer given for each
door -- it is a great hint to this riddle. The door to the treasure repository has the integer that
gives the larger key number. The key number of a positive integer n is the largest prime factor
minus the total sum of any other prime factors, where the prime factors are the prime numbers
that divide into n without leaving a remainder. Note that each prime factor should be counted
only once.

As an example, suppose there are doors with integers 30 and 20 respectively. Since 30 has three
prime factors 2, 3 and 5, its key number is 5 - (2 + 3) = 0. Similarly, since 20 has two prime
factors 2 and 5, its key number 20 is 5 - 2 = 3. Jimmy therefore should open the door with 20.

Your job is to write a program to help Jimmy by solving this riddle.

Input

The input is a sequence of datasets. Each dataset consists of a line that contains two integers a
and b separated by a space (2 ≤ a, b ≤ 106 ). It is guaranteed that key numbers of these integers
are always different.

The input is terminated by a line with two zeros. This line is not part of any datasets and thus
should not be processed.

Output

For each dataset, print in a line ‘a’ (without quotes) if the door with the integer a is connected
to the treasure repository; print ‘b’ otherwise. No extra space or character is allowed.

Sample Input

10 15
30 20
0 0

Output for the Sample Input

a
b



Sample input:
10 15
30 20
0 0


Sample output:
a
b

Submission status: Accepted

Solution code:
def f(n):
  a=set()
  i=2
  while i*i<=n:
    while n%i==0:
      a.add(i)
      n//=i
    i+=1
  if n>1: a.add(n)
  return a

while 1:
  a,b=map(int,input().split())
  if (a|b)==0: break
  a,b=f(a),f(b)
  print("a" if 2*max(a)-sum(a)>2*max(b)-sum(b) else "b")

Submission status: Accepted

Solution code:
import math

primes=[2]
top=2
nlist=[2*x-1 for x in range(2,500)]
while top<math.sqrt(500):
    top=nlist[0]
    primes.append(top)
    newnlist=[]
    for i in nlist:
        if i%top!=0:
            newnlist.append(i)
    nlist=newnlist
primes=primes+nlist

def getpoints(a):
    primelist=[]
    while a>1:
        primeflag=0
        for p in primes:
            if a%p==0:
                primeflag=1
                a=a/p
                if p not in primelist:
                    primelist.append(p)
                break
        if primeflag==0:
            primelist.append(a)
            a=1
    psorted=sorted(primelist)
    pts=primelist[-1]-sum(psorted[:-1])
    return pts
    
while(1):
    [a,b]=[int(x) for x in raw_input().split()]
    if a==0:
        break
    else:
        pta=getpoints(a)
        ptb=getpoints(b)
        if pta>ptb:
            print 'a'
        else:
            print 'b'

Submission status: Accepted

Solution code:
def prime(a):
    prime = []
    for p in range(2, a+1):
        if a % p == 0:
            prime.append(p)
            while a % p == 0:
                a /= p
    return prime

def keynumber(prime):
    sum = 0
    for i in range(len(prime) - 1):
        sum += prime[i]
    key = prime[-1] - sum
    return key

while 1:
    ab = raw_input().split()
    a = int(ab[0])
    b = int(ab[1])
    if a == 0 and b == 0:
        break
    pa = prime(a)
    pb = prime(b)
    ka = keynumber(pa)
    kb = keynumber(pb)
    if ka > kb:
        print('a')
    else:
        print('b')

Submission status: Accepted

Solution code:
import math
def Soinsu(a, b) :
    global soin
    while True :
        if a % b == 0 :
            soin.append(b)
            if a/b == 1 :
                break
            else :
                Soinsu(a/b, b)
                break
        else :
            b += 1
            if math.sqrt(a) < b :
                soin.append(int(a))
                break
    return soin

def calc(x) :
    x = list(set(x))
    x.sort(reverse=True)
    #print(x)
    if len(x) == 1 :
        return x[0]
    else :
        return x[0] - sum(x[1:])

while True :
    x, y = map(int, input().split())
    if x == 0 and y == 0 :
        break
    soin = []
    x_door = calc(Soinsu(x, 2))
    soin = []
    y_door = calc(Soinsu(y, 2))
    if x_door > y_door :
        print("a")
    else :
        print("b")

Submission status: Runtime Error

Solution code:
def prime(a):
    prime = []
    for p in range(2, a):
        if a % p == 0:
            prime.append(p)
            while a % p == 0:
                a /= p
    return prime

def keynumber(prime):
    sum = 0
    for i in range(len(prime) - 1):
        sum += prime[i]
    key = prime[-1] - sum
    return key

while 1:
    ab = raw_input().split()
    a = int(ab[0])
    b = int(ab[1])
    if a == 0 and b == 0:
        break
    pa = prime(a)
    pb = prime(b)
    ka = keynumber(pa)
    kb = keynumber(pb)
    if ka > kb:
        print('a')
    else:
        print('b')