【Python】AOJ-114 Electro-Flyについて

Question

AOJにおけるこちらの問題(AOJ-114)にて下記のコードで提出したのですがタイムアウトになってしまいました。

while 1:
    try:
        lst = list(map(int,input().split()))
        if sum(lst)==0:
            break
        lst = [[lst[0],lst[1]],[lst[2],lst[3]],[lst[4],lst[5]]]
        coordinate = [1,1,1]
        count = 0

        while 1:
            for i in range(3):
                coordinate[i] = (lst[i][0]*coordinate[i])%lst[i][1]
            count += 1
            # print(count)

            if coordinate==[1,1,1]:
                break
        
        print(count)
    except: break

理由は明らかに計算時間がかかりすぎている事だと思うのですが、短縮するような方法が思いつきません。
計算時間を短縮差可能な手法があれば教えていただきたいです。

Answer 1

xもyもzもそれぞれ一定の周期で1に戻ります。
全部が同時に1になるのはその周期が重なるタイミングなので、それぞれの周期を別々に求めて周期が重なるタイミングを計算すれば今のやり方より格段に速くなります。

Comments

[YMD_kts]

x,y,zがそれぞれ1に戻ってくる周期の最小公倍数を取ればいいってことですね！
なるほど！有難うございます！！

Answer 2

以下で AC しました。
x, y, z の戻ってくるまでの回数を計算して、最小公倍数を求めればよいです。

import math
import itertools
import functools


def lcm(a, b):
    """a と b の最小公倍数を計算する。
    """
    return a * b // math.gcd(a, b)


def calc_count(a, m):
    """パラメータ a, m のときに戻ってくるまでの反復回数を計算する。
    """
    x = 1  # 初期位置
    for i in itertools.count(1):
        x = (x * a) % m
        if x == 1:
            break

    return i


#######################################
# main
#######################################
while True:
    a1, m1, a2, m2, a3, m3 = list(map(int, input().split()))
    if a1 == 0:
        break

    # それぞれの周期を計算する。
    c1 = calc_count(a1, m1)
    c2 = calc_count(a2, m2)
    c3 = calc_count(a3, m3)

    # 最小公倍数を計算する。
    ans = functools.reduce(lcm, (c1, c2, c3))

    print(ans)