Problem:


電子蝿

 ある計算機学者が電子空間に棲息する電子蝿という奇妙な生命体を見つけました。電子蝿の行動を観察しているうちに、この空間の (x, y, z) 地点にいる電子蝿は、次に以下の規則で示される (x', y', z')に移動することが分かりました。

 ただし、a1, m1, a2, m2, a3, m3 は電子蝿の個体ごとに定まる正の整数です。A mod B は正の整数 A を正の整数 B で割ったときの余りです。

 さらに観察をすると、ある種の電子蝿は (1,1,1) に置いてからしばらくすると、必ず (1,1,1) に戻ってくることがわかりました。このような蝿を戻り蝿と名付けました(1) 。

戻り蝿のデータを入力とし、(1,1,1) に戻ってくる最小の移動回数 (>0) を出力するプログラムを作成してください。なお 1< a1, m1, a2, m2, a3, m3 < 215 とします。

(1)  a1 と m1, a2 と m2, a3 と m3 がそれぞれ互いに素 (公約数が 1) である時に戻ります。

Input

複数のデータセットが与えられます。各データセットは以下の形式で与えられます。

a1 m1 a2 m2 a3 m3

入力は６つの 0 を含む行で終わります。データセットの数は 50 を超えません。

Output

各データセットごとに、(1,1,1) に戻ってくる最小の移動回数(整数)を１行に出力してください。

Sample Input

2 5 3 7 6 13
517 1024 746 6561 4303 3125
0 0 0 0 0 0

Output for the Sample Input

12
116640000



Sample input:
2 5 3 7 6 13
517 1024 746 6561 4303 3125
0 0 0 0 0 0


Sample output:
12
116640000

Submission status: Time Limit Exceeded

Solution code:
from math import gcd

def get_loop(a, m):
  count = 1
  while a ** count % m != 1:
    count += 1
  return count

while True:
  a1, m1, a2, m2, a3, m3 = map(int, input().split())
  if not a1:
    break
  loop_a = get_loop(a1, m1)
  loop_b = get_loop(a2, m2)
  loop_c = get_loop(a3, m3)
  loop_ab = loop_a * loop_b // gcd(loop_a, loop_b)
  loop_abc = loop_ab * loop_c // gcd(loop_ab, loop_c)
  print(loop_abc)

Submission status: Time Limit Exceeded

Solution code:
from math import gcd

def get_loop(a, m):
  count = 1
  acc = a
  while acc % m != 1:
    count += 1
    acc *= a
  return count

while True:
  a1, m1, a2, m2, a3, m3 = map(int, input().split())
  if not a1:
    break
  loop_a = get_loop(a1, m1)
  loop_b = get_loop(a2, m2)
  loop_c = get_loop(a3, m3)
  loop_ab = loop_a * loop_b // gcd(loop_a, loop_b)
  loop_abc = loop_ab * loop_c // gcd(loop_ab, loop_c)
  print(loop_abc)

Submission status: Accepted

Solution code:
import itertools as I,math;
def lcm(x,y):return x*y//math.gcd(x,y);
while 1:
    a,b,c,d,e,f=map(int,input().split());
    if a==0:break;
    A=I.dropwhile(lambda x:1<pow(a,x,b),range(1,b));
    B=I.dropwhile(lambda x:1<pow(c,x,d),range(1,d));
    C=I.dropwhile(lambda x:1<pow(e,x,f),range(1,f));
    x,y,z=map(lambda u:list(u)[0],[A,B,C]);
    print(lcm(x,lcm(y,z)))

Submission status: Accepted

Solution code:
import math
from functools import reduce

def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

while(True):
    a1,m1,a2,m2,a3,m3 = map(int, input().split())
    if a1 == 0: break
    p = 1
    nx = 0
    while(True):
        nx += 1
        p = a1*p%m1
        if not p-1: break
    p = 1
    ny = 0
    while(True):
        ny += 1
        p = a2*p%m2
        if not p-1: break
    p = 1
    nz = 0
    while(True):
        nz += 1
        p = a3*p%m3
        if not p-1: break
    print(lcm(nx,ny,nz))

Submission status: Accepted

Solution code:
def f(a,b):
  p,q=a,b
  while q!=0: p,q=q,p%q
  return a/p*b
  
while 1:
  x=map(int,raw_input().split())
  if any(x)==0: break
  A=[]
  for i in range(0,6,2):
    c=1
    while pow(x[i],c,x[i+1])!=1: c+=1
    A.append(c)
  x=reduce(lambda a,b: f(a,b), A)
  print x

Submission status: Accepted

Solution code:
def f(a,b):
  p,q=a,b
  while q!=0: p,q=q,p%q
  return a/p*b
  
while 1:
  x=map(int,raw_input().split())
  if any(x)==0: break
  A=[]
  for i in range(0,6,2):
    a,b=x[i:i+2]
    c=1
    for j in range(1,b):
      c*=a; c%=b
      if c==1: break
    A.append(j)
  x=reduce(lambda a,b: f(a,b), A)
  print x

Submission status: Accepted

Solution code:
def f(a,b):
  p,q=a,b
  while q!=0: p,q=q,p%q
  return a/p*b
  
while 1:
  x=map(int,raw_input().split())
  if any(x)==0: break
  A=[]
  for i in range(0,6,2):
    a,b=x[i:i+2]
    c=1
    for j in range(1,b):
      c=(c*a)%b
      if c==1: break
    A.append(j)
  a,b,c=A
  print f(f(a,b),c)

Submission status: Accepted

Solution code:
def f(a,b):
  p,q=a,b
  while q!=0: p,q=q,p%q
  return a/p*b

def g(a,b):
  c,i=a%b,1
  while c!=1: i,c=i+1,(c*a)%b
  return i
  
while 1:
  x=map(int,raw_input().split())
  if any(x)==0: break
  a,b,c=[g(x[i],x[i+1]) for i in range(0,6,2)]
  print f(f(a,b),c)

Submission status: Accepted

Solution code:
# 0114

def gcd(a, b):
	if b == 0: return a
	return gcd(b, a % b)

def lcm(a, b):
	return a * b / gcd(a, b)

while True:
	try:
		x, y, z = 1, 1, 1
		c1, c2 ,c3 = 0, 0, 0
		a1, m1, a2, m2, a3, m3 = map(int, input().split())
		
		if sum([a1, m1, a2, m2, a3, m3]) == 0:
			break

		while True:
			x = a1 * x % m1
			c1 += 1
			if x == 1:
				break

		while True:
			y = a2 * y % m2
			c2 += 1
			if y == 1:
				break

		while True:
			z = a3 * z % m3
			c3 += 1
			if z == 1:
				break

		print(int(lcm(c1, lcm(c2, c3))))

	except EOFError:
		break

Submission status: Accepted

Solution code:
# 0114

def gcd(a, b):
	if b == 0: return a
	return gcd(b, a % b)

def lcm(a, b):
	return a * b / gcd(a, b)

def times(a, m):
	c = 1
	x = a * 1 % m
	while x != 1:
		x = a * x % m
		c += 1
	return c

while True:
	try:
		x, y, z = 1, 1, 1
		c1, c2 ,c3 = 0, 0, 0
		a1, m1, a2, m2, a3, m3 = map(int, input().split())
		
		if sum([a1, m1, a2, m2, a3, m3]) == 0:
			break

		c1 = times(a1, m1)
		c2 = times(a2, m2)
		c3 = times(a3, m3)

		print(int(lcm(c1, lcm(c2, c3))))

	except EOFError:
		break

Submission status: Accepted

Solution code:
# 0114

def gcd(a, b):
	if b == 0: return a
	return gcd(b, a % b)

def lcm(a, b):
	return a * b / gcd(a, b)

def times(a, m):
	c = 1
	x = a * 1 % m
	while x != 1:
		x = a * x % m
		c += 1
	return c

while True:
	x, y, z = 1, 1, 1
	c1, c2 ,c3 = 0, 0, 0
	a1, m1, a2, m2, a3, m3 = map(int, input().split())
	
	if sum([a1, m1, a2, m2, a3, m3]) == 0:
		break

	c1 = times(a1, m1)
	c2 = times(a2, m2)
	c3 = times(a3, m3)

	print(int(lcm(c1, lcm(c2, c3))))

Submission status: Accepted

Solution code:
# 0114

def gcd(a, b):
	if b == 0: return a
	return gcd(b, a % b)

def lcm(a, b):
	return a * b / gcd(a, b)

def times(a, m):
	c = 1
	x = a * 1 % m
	while x != 1:
		x = a * x % m
		c += 1
	return c

while True:
	a1, m1, a2, m2, a3, m3 = map(int, input().split())
	
	if sum([a1, m1, a2, m2, a3, m3]) == 0:
		break

	c1 = times(a1, m1)
	c2 = times(a2, m2)
	c3 = times(a3, m3)

	print(int(lcm(c1, lcm(c2, c3))))

Submission status: Accepted

Solution code:
def getfly(x,a,m,i):
        if x==1 and i!=0:
            return i
        else:
            return getfly((a*x)%m,a,m,i+1)

def getgcd(a,b):
    #print a,b
    (a,b)=max(a,b),min(a,b)
    if a%b==0:
        return b
    else:
        return getgcd(b,a%b)

while(1):
    indata=[int(x) for x in raw_input().split()]
    if indata[0]==0:
        break
    else:
        a=indata[0::2]
        m=indata[1::2]
        A=[]
        for j in range(3):
            i=0
            x=1
            p=a[j]
            q=m[j]
            while (x!=1 or i==0):
                i+=1
                x=p*x%q
            A.append(i)
        gab=getgcd(A[0],A[1])
        lab=A[0]*A[1]/gab
        gac=getgcd(A[2],lab)
        ans=A[2]*lab/gac
        print ans

Submission status: Accepted

Solution code:
def g(a,b):
    while b:a,b=b,a%b
    return a

def f(a,m,b):
    x=a
    while x!=1:
        x=a*x%m
        b+=1
    return b        

while 1:
    x,m,y,my,z,mz = map(int, input().split())
    if x==0:break
    a,b,c=f(x,m,1),f(y,my,1),f(z,mz,1)
    d=a*b/g(a,b)
    print(int(c*d/g(c,d)))

Submission status: Accepted

Solution code:
from decimal import *
class Fry:
    def __init__(self,a1,m1,a2,m2,a3,m3):
        self.a1 = a1
        self.m1 = m1
        self.a2 = a2
        self.m2 = m2
        self.a3 = a3
        self.m3 = m3

    def euc(self,m,n):
        if n==0:
            return(m)
        else:
            r = m % n
            return(self.euc(n,r))

    def test(self,a,m):
        n = 0
        x = 1
        while True:
            x1 = (a * x) % m
            n += 1
            if x1 == 1:
                break
            else:
                x = x1
        return(n)

    def mv(self):
        n1 = Decimal(self.test(self.a1,self.m1))
        n2 = Decimal(self.test(self.a2,self.m2))
        n3 = Decimal(self.test(self.a3,self.m3))
        m1 = n1*n2/self.euc(n1,n2)
        m2 = m1*n3/self.euc(m1,n3)

        return(m2)

while True:
    a1,m1,a2,m2,a3,m3 = list(map(int, input().strip().split()))
    if a1==m1==a2==m2==a3==m3==0:
        break
    fry = Fry(a1,m1,a2,m2,a3,m3)
    print(fry.mv())

Submission status: Accepted

Solution code:
def mcd(m,n):
    if n==0:
        return(m)
    else:
        r = m % n
    return(mcd(n,r))

def lcd(m,n):
    return(m * n // mcd(m, n))

class Fry:
    def __init__(self,a1,m1,a2,m2,a3,m3):
        self.a1 = a1
        self.m1 = m1
        self.a2 = a2
        self.m2 = m2
        self.a3 = a3
        self.m3 = m3


    def test(self,a,m):
        n = 0
        x = 1
        while True:
            x1 = (a * x) % m
            n += 1
            if x1 == 1:
                break
            else:
                x = x1
        return(n)

    def mv(self):
        n1 = self.test(self.a1,self.m1)
        n2 = self.test(self.a2,self.m2)
        n3 = self.test(self.a3,self.m3)
        m1 = lcd(n1,n2)
        m2 = lcd(m1,n3)

        return(m2)

while True:
    a1,m1,a2,m2,a3,m3 = list(map(int, input().strip().split()))
    if a1==m1==a2==m2==a3==m3==0:
        break
    fry = Fry(a1,m1,a2,m2,a3,m3)
    print(fry.mv())

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
import os
import math

def gcd(a, b):
    if b == 0: return a
    return gcd(b, a % b)

def lcm(a, b):
    return (a * b) // gcd(a, b)

def interval(a, m):
    cnt = 0
    x = 1
    while True:
        x = (a * x) % m
        cnt += 1
        if x == 1:
            return cnt

for s in sys.stdin:
    a1, m1, a2, m2, a3, m3 = map(int, s.split())
    if sum([a1, m1, a2, m2, a3, m3]) == 0:
        break

    x_num = interval(a1, m1)
    y_num = interval(a2, m2)
    z_num = interval(a3, m3)

    a = lcm(x_num, y_num)
    b = lcm(a, z_num)
    print(b)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0114
"""
import sys


def lcm(x, y):
    return x*y//gcd(x, y)


def gcd(x, y):
    if x < y:
        temp = x
        x = y
        y = temp
    while y > 0:
        r = x % y
        x = y
        y = r
    return x


def solve(data):
    a1, m1, a2, m2, a3, m3 = data
    x_cycle = y_cycle = z_cycle = 0
    x = y = z = 1

    while True:
        x = (a1 * x) % m1
        x_cycle += 1
        if x == 1:
            break
    while True:
        y = (a2 * y) % m2
        y_cycle += 1
        if y == 1:
            break
    while True:
        z = (a3 * z) % m3
        z_cycle += 1
        if z == 1:
            break

    return lcm(lcm(x_cycle, y_cycle), z_cycle)


def main(args):
    # data = [2, 5, 3, 7, 6, 13]
    #data = [517, 1024, 746, 6561, 4303, 3125]
    while True:
        data = [int(x) for x in input().split(' ')]
        if data.count(0) == 6:
            break
        result = solve(data)
        print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0114
"""
import sys


def lcm(x, y):
    return x*y//gcd(x, y)


def gcd(x, y):
    if x < y:
        temp = x
        x = y
        y = temp
    while y > 0:
        r = x % y
        x = y
        y = r
    return x


def calc_cycle(a, m):
    x = 1
    cycle = 0
    while True:
        x = (a * x) % m
        cycle += 1
        if x == 1:
            break
    return cycle


def solve(data):
    a1, m1, a2, m2, a3, m3 = data
    x_cycle = calc_cycle(a1, m1)
    y_cycle = calc_cycle(a2, m2)
    z_cycle = calc_cycle(a3, m3)

    return lcm(lcm(x_cycle, y_cycle), z_cycle)


def main(args):
    # data = [2, 5, 3, 7, 6, 13]
    #data = [517, 1024, 746, 6561, 4303, 3125]
    while True:
        data = [int(x) for x in input().split(' ')]
        if data.count(0) == 6:
            break
        result = solve(data)
        print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
from fractions import gcd
while True:
    a = list(map(int, input().split()))
    if a.count(0) == 6:
        break
    x = a[0] % a[1]
    ix = 1
    while x != 1:
        x = a[0] * x % a[1]
        ix += 1
    y = a[2] % a[3]
    iy = 1
    while y != 1:
        y = a[2] * y % a[3]
        iy += 1
    z = a[4] % a[5]
    iz = 1
    while z != 1:
        z = a[4] * z % a[5]
        iz += 1
    ixy = ix * iy // gcd(ix, iy)
    print(ixy * iz // gcd(ixy, iz))

Submission status: Accepted

Solution code:
def gcd(a, b):
    if b == 0: return a
    return gcd(b, a % b)

while True:
    a = list(map(int, input().split()))
    if a.count(0) == 6:
        break
    x = a[0] % a[1]
    ix = 1
    while x != 1:
        x = a[0] * x % a[1]
        ix += 1
    y = a[2] % a[3]
    iy = 1
    while y != 1:
        y = a[2] * y % a[3]
        iy += 1
    z = a[4] % a[5]
    iz = 1
    while z != 1:
        z = a[4] * z % a[5]
        iz += 1
    ixy = ix * iy // gcd(ix, iy)
    print(ixy * iz // gcd(ixy, iz))

Submission status: Accepted

Solution code:
def gcd(a, b):
    if b == 0: return a
    return gcd(b, a % b)

def rooptimes(ai, mi):
    x = ai % mi
    i = 1
    while x != 1:
        x = ai * x % mi
        i += 1
    return(i)

while True:
    a = list(map(int, input().split()))
    if a.count(0) == 6:
        break
    ix = rooptimes(a[0], a[1])
    iy = rooptimes(a[2], a[3])
    iz = rooptimes(a[4], a[5])

    ixy = ix * iy // gcd(ix, iy)
    print(ixy * iz // gcd(ixy, iz))

Submission status: Accepted

Solution code:
import sys
import os
import math

def lcm(a, b):
    return a*b//math.gcd(a,b)

def main():
    while True:
        a = input().split(" ")
        a1 = int(a[0])
        m1 = int(a[1])
        a2 = int(a[2])
        m2 = int(a[3])        
        a3 = int(a[4])
        m3 = int(a[5])
        if a1 is 0:
            break        
        i = 1
        xyz = [a1%m1, a2%m2, a3%m3]
        temp = [0, 0, 0]
        if math.gcd(a1, m1) is math.gcd(a2, m2) is math.gcd(a3, m3) is 1:
            while True:
                if xyz[0] is xyz[1] is xyz[2] is 1:
                    break
                i += 1
                xyz = [(xyz[0]*a1)%m1, (xyz[1]*a2)%m2, (xyz[2]*a3)%m3]
                if xyz[0] is 1:
                    temp[0] = i
                    xyz[0] = 0
                if xyz[1] is 1:
                    temp[1] = i
                    xyz[1] = 0
                if xyz[2] is 1:
                    temp[2] = i
                    xyz[2] = 0
                if xyz[0] is xyz[1] is xyz[2] is 0:
                    break
            tmp = lcm(temp[0], temp[1])
            tmp = lcm(tmp, temp[2])
            print(tmp)
        else:
            print("error")

main()

Submission status: Accepted

Solution code:
import sys


def PeriodCount(a, mod):
    x = a % mod
    count = 1

    while x != 1:
        x = a * x % mod
        count += 1

    return count


def GreatestCommonDiviser(num1, num2):
    while num2 != 0:
        num1, num2 = num2, num1 % num2

    return num1


def LeastCommonMultiple(num1, num2):
    return num1 * num2 / GreatestCommonDiviser(num1, num2)


for line in sys.stdin:
    line = line[:-1]

    if line == "0 0 0 0 0 0":
        break

    inputNum = [int(item) for item in line.split(" ")]
    counts = [PeriodCount(inputNum[lp * 2], inputNum[lp * 2 + 1])
              for lp in range(3)]

    lcm = LeastCommonMultiple(counts[0], counts[1])
    lcm = LeastCommonMultiple(lcm, counts[2])

    print(int(lcm))

Submission status: Accepted

Solution code:
import math

def get_input():
    while True:
        try:
            yield ''.join(input())
        except EOFError:
            break

def lcm(a,b):
    d = math.gcd(a,b)
    aa = int(a/d)
    bb = int(b/d)
    return aa*bb*d

while True:
    a1,m1,a2,m2,a3,m3 = [int(i) for i in input().split()]
    if a1 == 0 and m1 == 0 and a2 == 0 and m2 == 0 and a3 == 0 and m3 == 0:
        break

    x = 1
    y = 1
    z = 1
    cnt1 = 0
    cnt2 = 0
    cnt3 = 0

    while True:
        x = a1*x % m1
        cnt1 += 1
        if x == 1:
            break

    while True:
        y = a2*y % m2
        cnt2 += 1
        if y == 1:
            break

    while True:
        z = a3*z % m3
        cnt3 += 1
        if z == 1:
            break

    print(lcm(lcm(cnt1,cnt2),cnt3))

Submission status: Accepted

Solution code:
from math import gcd

def get_loop(a, m):
  count = 1
  acc = a
  while acc != 1:
    count += 1
    acc *= a
    acc %= m
  return count

def main():
  while True:
    a1, m1, a2, m2, a3, m3 = map(int, input().split())
    if not a1:
      break
    loop_a = get_loop(a1, m1)
    loop_b = get_loop(a2, m2)
    loop_c = get_loop(a3, m3)
    loop_ab = loop_a * loop_b // gcd(loop_a, loop_b)
    loop_abc = loop_ab * loop_c // gcd(loop_ab, loop_c)
    print(loop_abc)

main()

Submission status: Accepted

Solution code:
from math import gcd

def get_loop(a, m):
  count = 1
  acc = a
  while acc != 1:
    count += 1
    acc *= a
    acc %= m
  return count

while True:
  a1, m1, a2, m2, a3, m3 = map(int, input().split())
  if not a1:
    break
  loop_a = get_loop(a1, m1)
  loop_b = get_loop(a2, m2)
  loop_c = get_loop(a3, m3)
  loop_ab = loop_a * loop_b // gcd(loop_a, loop_b)
  loop_abc = loop_ab * loop_c // gcd(loop_ab, loop_c)
  print(loop_abc)

Submission status: Accepted

Solution code:
# AOJ 0114: Electro-Fly
# Python3 2018.6.18 bal4u

def gcd(a, b):
	if a < b: a, b = b, a
	while b > 0:
		r = a % b
		a, b = b, r
	return a

while True:
	a1, m1, a2, m2, a3, m3 = list(map(int, input().split()))
	if a1 == 0: break
	n = 0
	b1, b2, b3 = 1, 1, 1
	a, b, c = 0, 0, 0
	while True:
		if a == 0: b1 = (b1 * a1) % m1
		if b == 0: b2 = (b2 * a2) % m2
		if c == 0: b3 = (b3 * a3) % m3
		n += 1
		if a == 0 and b1 == 1: a = n
		if b == 0 and b2 == 1: b = n
		if c == 0 and b3 == 1: c = n
		if a != 0 and b != 0 and c != 0: break
	
	ans = a // gcd(a,b) * b
	ans = ans // gcd(ans, c) * c
	print(ans)

Submission status: Accepted

Solution code:
# AOJ 0114: Electro-Fly
# Python3 2018.6.18 bal4u

from math import gcd

while True:
	a1, m1, a2, m2, a3, m3 = list(map(int, input().split()))
	if a1 == 0: break
	n = 0
	b1, b2, b3 = 1, 1, 1
	a, b, c = 0, 0, 0
	while True:
		if a == 0: b1 = (b1 * a1) % m1
		if b == 0: b2 = (b2 * a2) % m2
		if c == 0: b3 = (b3 * a3) % m3
		n += 1
		if a == 0 and b1 == 1: a = n
		if b == 0 and b2 == 1: b = n
		if c == 0 and b3 == 1: c = n
		if a != 0 and b != 0 and c != 0: break
	
	ans = a // gcd(a,b) * b
	ans = ans // gcd(ans, c) * c
	print(ans)

Submission status: Accepted

Solution code:
def prime_gen():
    primes = []
    n = 2
    while True:
        is_prime = True
        for p in primes:
            if p * p > n:
                break
            if n % p == 0:
                is_prime = False
                break
        if is_prime:
            primes.append(n)
            yield n
        n += 1                

def lcm(numbers):
    result = 1
    for p in prime_gen():
        while True:
            if all(map(lambda n: n == 1, numbers)):
                return result
            if not any(map(lambda n: n % p == 0, numbers)):
                break
            result *= p
            numbers = [n if n % p != 0 else n / p for n in numbers]

def chain_len(a, m):
    count = 0
    n = 1
    while True:
        n = (a * n) % m
        count += 1
        if n == 1:
            return count

while True:
    fly = map(int, raw_input().split())
    if not any(fly): break

    counts = []
    for i in range(3):
        counts.append(chain_len(fly[2 * i], fly[2 * i + 1]))
    
    print lcm(counts)

Submission status: Accepted

Solution code:
import fractions
def func(a,m):
    x,n=1,1
    x=(a*x)%m
    while x!=1:
        x=(a*x)%m
        n+=1
    return n

def lcm(a,b):
    return a*b/fractions.gcd(a,b)

while True:
    a1,m1,a2,m2,a3,m3=map(int,raw_input().split())
    if a1==m1==a2==m2==a3==m3==0:break
    x,y,z=func(a1,m1),func(a2,m2),func(a3,m3)
    print reduce(lcm,[x,y,z])

Submission status: Accepted

Solution code:
from fractions import gcd
def lcm(a,b):
    return a*b/gcd(a,b)
while True:
    tmp = map(int, raw_input().split(" "))
    if all(t==0 for t in tmp):
        break
    b = []
    for a,m in zip(tmp[::2], tmp[1::2]):
        i, c = 1, a%m
        while c!=1:
            c = (a*c)%m
            i += 1
        b.append(i)
    print reduce(lcm,b)

Submission status: Accepted

Solution code:
from fractions import gcd
def lcm(a,b):
    return a*b/gcd(a,b)
def ge(a,m):
    for aa,mm in zip(a, m): 
        i, b = 1, aa%mm
        while b!=1:
            b = (aa*b)%mm
            i += 1
        yield i
while True:
    tmp = map(int, raw_input().split(" "))
    if all(t==0 for t in tmp):
        break
    print reduce(lcm,ge(tmp[::2],tmp[1::2]))

Submission status: Accepted

Solution code:
from fractions import gcd
def lcm(a,b):
    return a*b/gcd(a,b)
def ge(a,m):
        i, b = 1, a%m
        while b!=1:
            b = (a*b)%m
            i += 1
        return i
while True:
    tmp = map(int, raw_input().split(" "))
    if all(t==0 for t in tmp):
        break
    print reduce(lcm,(ge(a,m) for a,m in zip(tmp[::2],tmp[1::2])))

Submission status: Accepted

Solution code:
from fractions import gcd
def lcm(a,b):
    return a*b/gcd(a,b)
def ge(a,m):
        i, b = 1, a%m
        while b!=1:
            b = (a*b)%m
            i += 1
        return i
while True:
    tmp = map(int, raw_input().split(" "))
    if tmp[1] == 0:
        break
    print reduce(lcm,(ge(a,m) for a,m in zip(tmp[::2],tmp[1::2])))

Submission status: Accepted

Solution code:
from fractions import gcd
def lcm(a,b):
    return a*b/gcd(a,b)
def ge(a,m):
        i, b = 1, a%m
        while b!=1:
            b = (a*b)%m
            i += 1
        return i
while True:
    tmp = map(int, raw_input().split(" "))
    if not tmp[1]:
        break
    print reduce(lcm,(ge(a,m) for a,m in zip(tmp[::2],tmp[1::2])))

Submission status: Accepted

Solution code:
from fractions import gcd
def lcm(a,b):
    return a*b/gcd(a,b)
def f(a,m):
        i, b = 1, a%m
        while b!=1:
            b = (a*b)%m
            i += 1
        return i
while True:
    tmp = map(int, raw_input().split(" "))
    if not tmp[1]:
        break
    print reduce(lcm,map(f,tmp[::2],tmp[1::2]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin, exit


def cycle1(a, m):
    x = a % m
    i = 1
    while x != 1:
        x = a * x % m
        i += 1
    return i


def lcm2(m, n):
    # assert m >= n
    while n:
        m, n = n, m % n
    return m


def gcd3(m, n, o):
    # assert m >= n >= o
    g1 = m * n // lcm2(m, n)
    g2 = n * o // lcm2(n, o)
    if g1 > g2:
        return g1 * g2 // lcm2(g1, g2)
    return g1 * g2 // lcm2(g2, g1)


def count_cycle(a1, m1, a2, m2, a3, m3):
    cs = [cycle1(a1, m1), cycle1(a2, m2), cycle1(a3, m3)]
    cs.sort(reverse=True)
    return gcd3(*cs)


def main(readline=stdin.readline):
    while 1:
        data = [int(s) for s in readline().split()]
        if not data[0]:
            exit()
        print(count_cycle(*data))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def gcd(a,b):
	return a if b==0 else gcd(b,a%b)
	
while 1:
	a1,m1,a2,m2,a3,m3=map(int,raw_input().split())
	if a1==0:break
	x=y=z=1
	x=a1*x%m1
	y=a2*y%m2
	z=a3*z%m3
	cx=cy=cz=1
	while 1:
		if x!=1:
			x=a1*x%m1
			cx+=1
		if y!=1:
			y=a2*y%m2
			cy+=1
		if z!=1:
			z=a3*z%m3
			cz+=1
		if (x,y,z)==(1,1,1):
			break
	lcd=cx*cy/gcd(cx,cy)
	lcd=lcd*cz/gcd(lcd,cz)
	print lcd

Submission status: Accepted

Solution code:
def gcd(a,b):
	return a if b==0 else gcd(b,a%b)
	
while 1:
	a1,m1,a2,m2,a3,m3=map(int,raw_input().split())
	if a1==0:break
	x=y=z=1
	x=a1*x%m1
	y=a2*y%m2
	z=a3*z%m3
	cx=cy=cz=1
	while x!=1:
		x=a1*x%m1
		cx+=1
	while y!=1:
		y=a2*y%m2
		cy+=1
	while z!=1:
		z=a3*z%m3
		cz+=1
	lcd=cx*cy/gcd(cx,cy)
	lcd=lcd*cz/gcd(lcd,cz)
	print lcd

Submission status: Accepted

Solution code:
def gcd(a,b):
	return a if b==0 else gcd(b,a%b)
	
while 1:
	a1,m1,a2,m2,a3,m3=map(int,raw_input().split())
	if a1==0:break
	x,y,z=a1%m1,a2%m2,a3%m3
	cx=cy=cz=1
	while x!=1:
		x=a1*x%m1
		cx+=1
	while y!=1:
		y=a2*y%m2
		cy+=1
	while z!=1:
		z=a3*z%m3
		cz+=1
	lcd=cx*cy/gcd(cx,cy)
	lcd=lcd*cz/gcd(lcd,cz)
	print lcd

Submission status: Accepted

Solution code:
def gcd(a,b):
	return a if b==0 else gcd(b,a%b)

def lcm(a,b):
	return a*b/gcd(a,b)
	
while 1:
	a1,m1,a2,m2,a3,m3=map(int,raw_input().split())
	if a1==0:break
	x,y,z=a1%m1,a2%m2,a3%m3
	cx=cy=cz=1
	while x!=1:
		x=a1*x%m1
		cx+=1
	while y!=1:
		y=a2*y%m2
		cy+=1
	while z!=1:
		z=a3*z%m3
		cz+=1
	print reduce(lcm,[cx,cy,cz])

Submission status: Accepted

Solution code:
from fractions import gcd
def lcm(a,b):
	return a*b/gcd(a,b)
	
while 1:
	a1,m1,a2,m2,a3,m3=map(int,raw_input().split())
	if a1==0:break
	x,y,z=a1%m1,a2%m2,a3%m3
	cx=cy=cz=1
	while x!=1:
		x=a1*x%m1
		cx+=1
	while y!=1:
		y=a2*y%m2
		cy+=1
	while z!=1:
		z=a3*z%m3
		cz+=1
	print reduce(lcm,[cx,cy,cz])

Submission status: Accepted

Solution code:
from fractions import gcd
def lcm(a,b):
	return a*b/gcd(a,b)
	
while 1:
	inp=map(int,raw_input().split())
	if inp[0]==0:break
	am=zip(inp[::2],inp[1::2])
	count=[0]*3
	for i in range(3):
		a,m=am[i]
		w,c=a%m,1
		while w!=1:
			w=a*w%m
			c+=1
		count[i]=c
	print reduce(lcm,count)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from fractions import gcd

"""
問題文の式から、オイラーの定理
	a^{\phi(n)} = 1 mod n

よって、\phi(n) の最小公倍数を求めればよい
"""

def lcm(a, b):
    return a * b / gcd(a, b)

def interval(ax, mx):
	p = 1
	cnt = 0
	while True:
		p = (p * ax) % mx
		cnt += 1
		if p == 1:
			return cnt

for line in sys.stdin:
	dset = map(int, line.split())
	if not any(dset):
		break
	a1, m1, a2, m2, a3, m3 = dset
	e = [interval(a1, m1), interval(a2, m2), interval(a3, m3)]
	# 3つの循環の最小公倍数を求める
	e.sort(reverse=True)
	print reduce(lcm, e)

Submission status: Accepted

Solution code:
def gcd(m, n):
    while n:
        m, n = n, m % n
    return m
def lcm(m, n):
    return m // gcd(m, n) * n

def f(a, m):
    x = a
    cnt = 1
    while x != 1:
        x = x * a % m
        cnt += 1
    return cnt

while 1:
    a1, m1, a2, m2, a3, m3 = map(int, input().split())
    if a1 == 0:
        break
    t1 = f(a1, m1)
    t2 = f(a2, m2)
    t3 = f(a3, m3)
    print(lcm(t1, lcm(t2, t3)))

Submission status: Accepted

Solution code:
def gcd(a, b):
    if a < b: a, b = b, a
    while b > 0:
        r = a % b
        a, b = b, r
    return a

def lcm(a,b):
    return ((a*b) // gcd(a,b))

def getCnt(a,m):
    cnt = 0
    n = 1
    while(1):
        n = (a * n) % m
        cnt += 1
        if n == 1:
            return cnt

while(1):
    a1,m1,a2,m2,a3,m3 = (int(x) for x in input().split())
    if a1 == 0:
        break
    x = y = z = 1
    cnt1 = getCnt(a1,m1)
    cnt2 = getCnt(a2,m2)
    cnt3 = getCnt(a3,m3)

    ans = lcm(cnt1,cnt2)
    ans = lcm(ans,cnt3)
    print(ans)

Submission status: Accepted

Solution code:
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop
import copy
from test.support import _MemoryWatchdog

BIG_NUM = 2000000000
HUGE_NUM = 99999999999999999
MOD = 1000000007
EPS = 0.000000001
sys.setrecursionlimit(100000)


#最大公約数
def gcd(x,y):
    x = abs(x)
    y = abs(y)

    if x < y:
        x,y = y,x

    if y == 0:
        return x
    else:
        return gcd(y,x%y)


#最小公倍数
def lcm(x,y):

    return (x*y)//(gcd(x,y))


A = [None]*3
M = [None]*3
cycle = [None]*3


while True:
    A[0],M[0],A[1],M[1],A[2],M[2] = map(int,input().split())
    if A[0] == 0 and M[0] == 0 and A[1] == 0 and M[1] == 0 and \
        A[2] == 0 and M[2] == 0:
        break

    for i in range(3):
        count = 0
        x = 1
        while True:
            x = (A[i]*x)%M[i]
            count += 1
            if x == 1:
                break
        cycle[i] = count

    ans = 1 #3つの周期の最小公倍数
    for i in range(3):
        ans = lcm(ans,cycle[i])

    print("%d"%(ans))

Submission status: Accepted

Solution code:
import math


def loop(a, x, m):
    count = 0
    while 1:
        count += 1
        x = (a * x) % m
        if x == 1: break
    return count


while 1:
    a1, m1, a2, m2, a3, m3 = map(int, input().split())
    if a1 == 0: break
    x = y = z = 1
    x = loop(a1, x, m1)
    y = loop(a2, y, m2)
    z = loop(a3, z, m3)
    xy = int(x * y / math.gcd(x, y))
    xyz = int(xy * z / math.gcd(xy, z))
    print(xyz)

Submission status: Accepted

Solution code:
import math
while 1:
    a1,m1,a2,m2,a3,m3=map(int,input().split())
    if a1==m1==a2==m2==a3==m3==0:break
    i=1
    x,y,z=0,0,0
    while 1:
        i=(a1*i)%m1
        x+=1
        if i==1:break
    while 1:
        i=(a2*i)%m2
        y+=1
        if i==1:break
    while 1:
        i=(a3*i)%m3
        z+=1
        if i==1:break
    xy=int(x*y/math.gcd(x,y))
    xyz=int(xy*z/math.gcd(xy,z))
    print(xyz)

Submission status: Accepted

Solution code:
import math
from functools import reduce

def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

while True:
    a1, m1, a2, m2, a3, m3 = map(int, input().split())
    if a1 == 0:
        break
    a = [a1, a2, a3]
    m = [m1, m2, m3]
    cyc = [0, 0, 0]
    for i in range(3):
        xyz = 1
        j = 0
        while True:
            j += 1
            xyz = a[i]*xyz%m[i]
            if xyz == 1:
                cyc[i] = j
                break
    print(lcm(*cyc))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(2**16)


def getfly(x,a,m,i):
        if x==1 and i!=0:
            return i
        else:
            return getfly((a*x)%m,a,m,i+1)

def getgcd(a,b):
    #print a,b
    (a,b)=max(a,b),min(a,b)
    if a%b==0:
        return b
    else:
        return getgcd(b,a%b)

while(1):
    indata=[int(x) for x in raw_input().split()]
    if indata[0]==0:
        break
    else:
        a=indata[0::2]
        m=indata[1::2]
        A=[]
        for i in range(3):
            A.append(getfly(1,a[i],m[i],0))
        #print A
        gab=getgcd(A[0],A[1])
        lab=A[0]*A[1]/gab
        gac=getgcd(A[2],lab)
        ans=A[2]*lab/gac
        print ans

Submission status: Runtime Error

Solution code:
def fly(x, y, z):
    global count
    _x = a1*x - m1 * (a1*x / m1)
    _y = a2*y - m2 * (a2*y / m2)
    _z = a3*z - m3 * (a3*z / m3)
    count += 1
    if _x == 1 and _y == 1 and _z == 1:
        print count
        return
    else:
        fly(_x, _y, _z)

while True:
    a1, m1, a2, m2, a3, m3 = map(int, raw_input().split(' '))
    if a1 == 0 and m1 == 0 and \
       a2 == 0 and m2 == 0 and \
       a3 == 0 and m3 == 0:
        break
    count = 0
    fly(1, 1, 1)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

import sys
import os
import math

def lcm(a, b):
    return (a * b) // math.gcd(a, b)

for s in sys.stdin:
    a1, m1, a2, m2, a3, m3 = map(int, s.split())
    if a1 == m1 == a2 == m2 == a3 == m3 == 0:
        break

    x = 1
    y = 1
    z = 1

    x_num = 0
    while True:
        x = (a1 * x) % m1
        x_num += 1
        if x == 1:
            break

    y_num = 0
    while True:
        y = (a2 * y) % m2
        y_num += 1
        if y == 1:
            break

    z_num = 0
    while True:
        z = (a3 * z) % m3
        z_num += 1
        if z == 1:
            break

    a = lcm(x_num, y_num)
    b = lcm(a, z_num)
    print(b)