[数据结构与算法]String LCM----Python题解

Let's define a multiplication operation between a string?aa?and a positive integer?xx:?a \cdot xa?x?is the string that is a result of writing?xx?copies of?aa?one after another. For example, "abc"?\cdot~2~=??2?=?"abcabc", "a"?\cdot~5~=??5?=?"aaaaa".

A string?aa?is divisible by another string?bb?if there exists an integer?xx?such that?b \cdot x = ab?x=a. For example, "abababab" is divisible by "ab", but is not divisible by "ababab" or "aa".

LCM of two strings?ss?and?tt?(defined as?LCM(s, t)LCM(s,t)) is the shortest non-empty string that is divisible by both?ss?and?tt.

You are given two strings?ss?and?tt. Find?LCM(s, t)LCM(s,t)?or report that it does not exist. It can be shown that if?LCM(s, t)LCM(s,t)?exists, it is unique.

Input

The first line contains one integer?qq?(1 \le q \le 20001≤q≤2000) — the number of test cases.

Each test case consists of two lines, containing strings?ss?and?tt?(1 \le |s|, |t| \le 201≤∣s∣,∣t∣≤20). Each character in each of these strings is either 'a' or 'b'.

Output

For each test case, print?LCM(s, t)LCM(s,t)?if it exists; otherwise, print?-1. It can be shown that if?LCM(s, t)LCM(s,t)?exists, it is unique.

Note

In the first test case, "baba" = "baba" ???1=??1?=?"ba"???2.

In the second test case, "aaaaaa" = "aa" ??3?=?"aaa"??2.

?这道题的大意是，输入求出两个字符串整除的最短的非空串。比如baba,ba两个字符串的整除最短非空串baba，跟我们的求最小公倍数相似

? 题解：使用python math库的gcd求出最大公约数，使用另一个字符串的字符数除这个最大公约数，得到的一个新的字符串，重复操作另一个字符串。得到的两个字符串相同的话，就是我们想要的两个字符串整除的最短的非空串。不同的话输出-1。

import math
n=int(input())
for i in range(n):
    num1=input()
    num2=input()
    gcd1=math.gcd(len(num1),len(num2)) #最大公约数
    num11=num1*(len(num2)//gcd1) #新的字符串
    num22=num2*(len(num1)//gcd1) #新的字符串
    if num11==num22:
        print(num11)
    else:
        print(-1)