TopCoder SRM 658 Div2 Easy: InfiniteString

これは簡単だった。

問題はこちら。

問題

文字列sを無限に繰り返したものをf(s) = s + s + s ....とする。
2つの文字列sとtを与えるのでf(s) == f(t)であるかどうかを答えよ。

解法

LCMを用いて、それぞれの文字列を繰り返して、２つの文字列の長さをそろえる。
あとはその文字列が同じになっているかどうかを確認すればいい。

def gcd(a, b):
    while b: a, b = b, a % b
    return a

def lcm(a, b):
    return a * b / gcd(a, b)
    
def equal(self, s, t):
    a, b = len(s), len(t)
    s = s * (lcm(a, b) / a)
    t = t * (lcm(a, b) / b)
    return "Equal" if s == t else "Not equal"

まとめ

Div2Easyらしい問題