15758. 무한 문자열

15758. 무한 문자열

문제

풀이

이 문제의 키포인트는 최소공배수이다. 즉 ababab, abab에서 문자열 길이는 6, 4이고 최소공배수는 12인 것을 알 수 있다. 즉 각 문자열을 12까지 반복하면 무한대일 때의 결과를 알 수 있다.
abababababab, abababababab가 12일 때이고 둘이 같으므로 무한대에서도 같다고 볼 수 있다.
반면에 ababab, abba를 보자 최소공배수는 12이므로
abababababab, abbaabbaabba이다. 서로 다르므로 무한대에서도 다르다고 볼 수 있다.

import math
T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    tmp = input().split(" ")
    s1, s2 = tmp[0], tmp[1]
    gcd = math.gcd(len(s1), len(s2))
    lcm = (len(s1) // gcd) * (len(s2) // gcd) * gcd
    if (s1 * (lcm // len(s1))) == (s2 * (lcm // len(s2))):
        print("#" + str(test_case) + " " + "yes")
    else:
        print("#" + str(test_case) + " " + "no")