Problem:


Score : 300 points

Problem Statement

You are given a string S of length N and another string T of length M.
These strings consist of lowercase English letters.

A string X is called a good string when the following conditions are all met:

Let L be the length of X. L is divisible by both N and M.

Concatenating the 1-st, (\frac{L}{N}+1)-th, (2 \times \frac{L}{N}+1)-th, ..., ((N-1)\times\frac{L}{N}+1)-th characters of X, without changing the order, results in S.

Concatenating the 1-st, (\frac{L}{M}+1)-th, (2 \times \frac{L}{M}+1)-th, ..., ((M-1)\times\frac{L}{M}+1)-th characters of X, without changing the order, results in T.

Determine if there exists a good string. If it exists, find the length of the shortest such string.

Constraints

1 \leq N,M \leq 10^5

S and T consist of lowercase English letters.

|S|=N

|T|=M

Input

Input is given from Standard Input in the following format:

N M
S
T

Output

If a good string does not exist, print -1; if it exists, print the length of the shortest such string.

Sample Input 1

3 2
acp
ae

Sample Output 1

6

For example, the string accept is a good string.
There is no good string shorter than this, so the answer is 6.

Sample Input 2

6 3
abcdef
abc

Sample Output 2

-1

Sample Input 3

15 9
dnsusrayukuaiia
dujrunuma

Sample Output 3

45



Sample input:
3 2
acp
ae


Sample output:
6

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import collections
import itertools as it
import math
#import numpy as np

#  = int(input())
n, m = map(int, input().split())
s = input()
t = input()
#  = list(map(int, input().split()))
#  = [int(input()) for i in range(N)]
#
# c = collections.Counter()
#a,bの最大公約数
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

g = gcd(n, m) 
a = n // g
b = m // g
for i in range(g):
    if s[i*a] != t[i*b]:
        print(-1)
        break
else:
    print(n * m // g)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import fractions

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

N, M = map(int, input().split())
S = input()
T = input()
if S[0] != T[0]:
    print(-1)
    exit()

l = lcm(N, M)

Moji = {}
Moji[0] = S[0]

for i in range(1, N):
    index = i * (l//N) + 1
    Moji[index-1] = S[i]

for i in range(1, M):
    index = i * (l//M) + 1
    if index-1 in Moji and Moji[index-1] != T[i]:
        print(-1)
        exit()

print(l)

Submission status: Accepted

Solution code:
from fractions import gcd

n, m = map(int, input().split())

s = input()
t = input()

# accept
# a c p
# a  e

g = gcd(n, m)
a = n // g
b = m // g
for i in range(g):
    if s[i*a] != t[i*b]:
        print(-1)
        exit()

print(n*m//g)

Submission status: Accepted

Solution code:
from fractions import gcd
N,M=map(int,input().split())
S=input()
T=input()
g=gcd(N,M)
n=N//g
m=M//g
for i in range(g):
    if S[i*n]!=T[i*m]:
        print(-1)
        break
else:
    print(n*m*g)

Submission status: Accepted

Solution code:
from fractions import gcd
n, m = map(int, input().split())
s = list(input())
t = list(input())
i = 1
ans = n * m // gcd(n, m)
g = gcd(n, m)
for i in range(g):
    if s[i * n // g] != t[i * m // g]:
        ans = -1
        break
print(ans)

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
ni = lambda:int(input())
import collections
import math
import fractions
gcd = fractions.gcd
n,m = ma()
s = input()
t = input()
l = m*n //gcd(m,n)
ln = []
for i in range(n):
    ln.append((l//n*i+1,s[i]))

for i in range(m):
    ln.append((l//m*i+1,t[i]))
ln.sort()
prev=-1
wp = ""
for num,w in ln:
    if num==prev:
        if w ==wp:
            pass
        else:
            print(-1)
            exit()
    prev=num
    wp = w
print(l)

Submission status: Accepted

Solution code:
A,B=list(map(int,input().split()))
l_a=list(input())
l_b=list(input())
import fractions
gcd=fractions.gcd(A,B)
total=A*B//gcd
A_n=total//A
B_n=total//B
S=A_n*B_n//fractions.gcd(A_n,B_n)
for i in range(total//S):
   if l_a[i*B_n] != l_b[i*A_n]:
      print(-1)
      exit()
print(total)

Submission status: Accepted

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True


# ワーシャルフロイド (任意の2頂点の対に対して最短経路を求める)
# 計算量n^3 (nは頂点の数)
def warshall_floyd(d, n):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d


# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定



# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret


# ここから書き始める
n, m = map(int, input().split())
s = input()
t = input()
l = lcm(n, m)
yes = True
if n == m and s != t:
    yes = False
elif n > m:
    for i in range(m):
        if i * n / m == int(i * n / m) and t[i] != s[int(i * n / m)]:
            # print(t[i], s[i * (n // m)])
            yes = False
else:
    for i in range(n):
        if i * m / n == int(i * m / n) and s[i] != t[int(i * m / n)]:
            yes = False
if yes:
    print(l)
else:
    print(-1)

Submission status: Accepted

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

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

n, m = map(int, input().split())
s = str(input())
t = str(input())
g = gcd(n, m)
l = lcm(n, m)
for i in range(g):
    if s[i*n//g] != t[i*m//g]:
        print(-1)
        break
else:
    print(l)

Submission status: Accepted

Solution code:
def gcd(a, b):
    c = a%b
    while(c != 0):
        a = b
        b = c
        c = a%b
    return b

def answer(s, t):
    a = len(s)
    b = len(t)
    if s[0] != t[0]:
        return -1
    if a < b:
        temp = a
        a = b
        b = temp
        temp = s
        s = t
        t = temp
    gcdAB = gcd(a, b)
    if gcdAB == 1:
        return a*b
    else:
        stack = 0
        sl = (gcdAB * (a//gcdAB) * (b//gcdAB))
        aJump = sl//a
        bJump = sl//b
        for i in range(b):
            if stack%aJump == 0:
                if s[stack//aJump] != t[i]:
                    return -1
            stack = bJump*(i+1)
        return sl
                

sl, tl = map(int, input().split())
s = input()
t = input()
print(answer(s, t))

Submission status: Accepted

Solution code:
from fractions import gcd

n, m = map(int, input().split())
s = list(map(str, input().rstrip()))
t = list(map(str, input().rstrip()))

g = gcd(n, m)

print(n * m // g if s[::n // g] == t[::m // g] else -1)

Submission status: Accepted

Solution code:
from fractions import gcd
N,M=map(int,input().split(' '))
S=input()
T=input()
G=gcd(N,M)
L = N*M//G
ln = list(range(0,L,(N//G)))
lm = list(range(0,L,(M//G)))
for i,j in zip(ln,lm):
    if i>=N or j>=M:
        break
    if S[i] != T[j]:
        print(-1)
        exit()
print(L)

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,M=MI()
    S=ST()
    T=ST()
    lcm = N*M//(gcd(N,M))
    ans = defaultdict(str)
    for i,s in enumerate(S):
        ans[i*lcm//N] = s
    for i,t in enumerate(T):
        if(ans[i*lcm//M] not in (t,"")):
            print(-1)
            return 
    print(lcm)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from fractions import gcd 
n,m = map(int,input().split())
s = input()
t = input()
g = gcd(n,m)
for i in range(g):
  if s[n//g*i] != t[m//g*i]:
    print(-1)
    exit()
print(n*m//g)

Submission status: Accepted

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

N,M=map(int,input().split())
S=input()
T=input()

C=N*M//gcd(max(N,M),min(N,M))
n=C//N
m=C//M

i=0
j=0
ans=C
while i<C and j<C:
    if  i==j:
        if S[i//n]!=T[j//m]:
            ans=-1
        i+=n
        j+=m
    elif i<j:
        i+=n
    else:
        j+=m
print(ans)

Submission status: Accepted

Solution code:
n , m = map(int, input().split())
s = input()
t = input()

def gcd(num1,num2):
    r=1
    while r!=0:
        r=num1%num2
        num1=num2
        num2=r
    return num1

def lcm(num1,num2):
    return num1*num2//gcd(num1,num2)

g1 = lcm(n,m)
g2 = lcm(g1//n,g1//m)

for i in range(g1//g2):
    if s[g2*n*i//g1]!=t[g2*m*i//g1]:
        print('-1')
        exit()
print(g1)

Submission status: Accepted

Solution code:
from fractions import gcd
n,m=map(int,input().split())
s=input()
t=input()
g=gcd(n,m)
ans=n*m//g
stepn=n//g
stepm=m//g
for i in range(g):
    if s[stepn*i]!=t[stepm*i]:print(-1);exit()
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
N,M = map(int,input().split())
s = input()
t = input()
n = N//gcd(N,M)
m = M//gcd(N,M)
for i in range(gcd(N,M)):
    if s[i*n] == t[i*m]:
        continue
    else:
        print(-1)
        break
else:
    print(N*M//gcd(N,M))

Submission status: Accepted

Solution code:
def make_divisors(n):
    divisors = set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.add(i)
            if i != n // i:
                divisors.add(n//i)
    return divisors

N,M = (int(x) for x in input().split())
S = list(input())
T = list(input())
if M > N:
    N,M = M,N
    S,T = T,S
dn = make_divisors(N)
dm = make_divisors(M)
dnm = dn & dm
if dnm == {1}:
    if S[0] == T[0]:
        print(N*M)
    else:
        print('-1')
else:
    gcd = max(dnm)
    n = N // gcd
    m = M // gcd
    for i in range(N//n):
        if S[n*i] != T[m*i]:
            print('-1')
            break
    else:
        print(N*M//gcd)

Submission status: Accepted

Solution code:
from fractions import gcd
n,m = map(int,input().split())
s = input()
t = input()

len_x = n*m//gcd(n,m)

li = set([i*(len_x//n)+1 for i in range(n)])&set([j*(len_x//m)+1 for j in range(m)])

for l in li:
    if s[(l-1)//(len_x//n)]!=t[(l-1)//(len_x//m)]:
        print(-1);exit()
print(len_x)

Submission status: Accepted

Solution code:
from fractions import gcd
n,m=map(int,input().split())
s=input()
t=input()
g=gcd(n,m)
l=n*m//g
for i in range(n):
  if i%(n//g)==0 and not s[i]==t[i*m//n]:
    print(-1)
    exit()
print(l)

Submission status: Accepted

Solution code:
import fractions

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

N, M = map(int, input().split())
S = input()
T = input()

d_N = {}

for n in range(N):
    d = fractions.gcd(n, N)
    d_N[(n // d, N // d)] = n

for m in range(M):
    d = fractions.gcd(m, M)
    k = (m // d, M // d)
    if k in d_N:
        if S[d_N[k]] != T[m]:
            print(-1)
            exit()

L = int(lcm(N, M))
print(L)

Submission status: Accepted

Solution code:
from  fractions  import gcd
n,m = map(int,input().split())
s = input()
t = input()
def lcm(x,y):
  return (x*y)//gcd(x,y)

a = lcm(n,m)
b = gcd(n,m)
if b==1:
  if s[0]==t[0]:
    print(a)
  else:
    print(-1)
else:
  k = int(a//b)
  for i in range(b):
    w = int(n*i//b)
    ww = int(m*i//b)
    if s[w]==t[ww]:
      continue
    else:
      print(-1)
      exit()
  else:
    print(a)

Submission status: Accepted

Solution code:
# A - Two Abbreviations
from fractions import gcd

N,M = map(int,input().split())
S = input()
T = input()

GCD = gcd(len(S),len(T))
LCM = len(S) * len(T) // GCD
ans = LCM

for i in range(GCD):
    if S[i*len(S)//GCD]!=T[i*len(T)//GCD]:
        ans = -1
        break

print(ans)

Submission status: Accepted

Solution code:
import sys
from fractions import gcd

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, M = map(int, input().split())
    S = input()
    T = input()
    L = M // gcd(M, N) * N
    G = gcd(M, N)
    n = N // G
    m = M // G

    for i in range(G):
        if S[n * i] == T[m * i]:
            continue
        else:
            print(-1)
            return

    print(L)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import fractions
N,M = [int(hoge) for hoge in input().split()]
S = input()
T = input()
G = fractions.gcd(N,M)
print(N*M//G) if S[::N//G] == T[::M//G] else print(-1)

Submission status: Accepted

Solution code:
import fractions

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

def main():
    N, M = map(int, input().split())
    S = input()
    T = input()

    L = lcm(N, M)
    ln = L//N
    lm = L//M
    n = {1+i*ln: s for i, s in enumerate(S)}
    m = {1+i*lm: t for i, t in enumerate(T)}
    
    for k in set(n.keys()).intersection(set(m.keys())):
        if n[k] != m[k]:
            return -1

    return L

print(main())

Submission status: Accepted

Solution code:
import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
def myAnswer(N:int,M:int,S:str,T:str) -> int:
   a = N//fractions.gcd(N,M)
   b =M // fractions.gcd(N,M)
   # print(a,b)
   for i in range(fractions.gcd(N,M)):
      # print(S[a * i],T[b * i])
      if(S [a * i] != T[b * i]):
         return -1
   else:
      return lcm(N,M)

def modelAnswer():
   return
def main():
   N,M = map(int,input().split())
   S = input()
   T = input()
   print(myAnswer(N,M,S,T))
if __name__ == '__main__':
   main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=str(input())
t=str(input())
def gcd(x, y):
    if x % y == 0:
        return(y)
    else:
        return gcd(y,x%y)
def lcm(a,b):
    return a*b//gcd(a,b)
a=n//gcd(n,m)
b=m//gcd(n,m)
for i in range(gcd(n,m)):
    if s[a*i]!=t[b*i]:
        print("-1")
        exit()
print(lcm(n,m))

Submission status: Accepted

Solution code:
from fractions import gcd
N, M = map(int, input().split())
S = input()
T = input()

g = gcd(N, M)
ans = N*M // g
N //= g
M //= g

if S[0] != T[0] or not all(i == j for i, j in zip(S[N::N], T[M::M])):
    ans = -1
print(ans)

Submission status: Accepted

Solution code:
import fractions
n,m=map(int,input().split())
s=input()
t=input()
b=0
for i in range(n):
    if (i*m)%n==0 and (i*m)//n<m:
        if not t[(i*m)//n]==s[i]:
            b=1

if b:
    print(-1)
else:
    print(n*m//fractions.gcd(n,m))

Submission status: Accepted

Solution code:
def gcd(a, b):
    big = max(a, b)
    small = min(a, b)
    
    r = small
    while r != 0:
        r = big % small
        big = small
        small = r
    
    return big
    
def lcm(a, b):
    gcd_num = gcd(a, b)
    return (a // gcd_num) * (b // gcd_num) * gcd_num

def main():
    n, m = map(int, input().split())
    s = input()
    t = input()
    
    a = n // gcd(n, m)
    b = m // gcd(n, m)
    lcm_num = lcm(n, m)
    
    ans = lcm_num
    for i in range(n // a):
        if s[a * i] != t[b * i]:
            ans = -1
            break
    
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import fractions
import bisect
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
N, M = map(int, input().split())
S = input()
T = input()
L = lcm(N,M)
S_arr = [0]*N
T_arr = [0]*M
for i in range(1,N):
    S_arr[i] = i*(L//N)
for i in range(1,M):
    T_arr[i] = i*(L//M)
if M <= N:
    for i in range(M):
        index = bisect.bisect_left(S_arr,T_arr[i])
        if S_arr[index] == T_arr[i] and S[index] != T[i]:
            print(-1)
            exit()
else:
    for i in range(N):
        index = bisect.bisect_left(T_arr,S_arr[i])
        if T_arr[index] == S_arr[i] and T[index] != S[i]:
            print(-1)
            exit()

print(L)

Submission status: Accepted

Solution code:
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions

import copy

# import heapq
# from collections import deque
# import decimal

sys.setrecursionlimit(10000001)
INF = sys.maxsize
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    def euclid(a, b):
        if b == 0:
            return a
        else:
            return euclid(b, a % b)

    def multiple(a, b):
        return a * b // euclid(a, b)

    n, m = ns()
    s = list(input())
    t = list(input())

    gcd = multiple(n, m)

    s_idx = [gcd // n * i for i in range(n)]
    t_idx = [gcd // m * i for i in range(m)]
    t_set = set(t_idx)

    for idx in s_idx:
        if idx in t_set:
            if s[idx * n // gcd] != t[idx * m // gcd]:
                print(-1)
                exit(0)

    print(gcd)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import functools, fractions
def lcm(a, b):
	return a * b // fractions.gcd(a, b)
def check(L, NM):
    res = []
    for i in range(NM):
        res.append(int(i*(L/NM)+1))
    return res
def check2(x, L, NM):
    return int((x-1)*NM/L)
def main():
    N,M = map(int,input().split())
    S = input()
    T = input()
    L = lcm(N,M)
    ans = L
    a = list(set(check(L, N)) & set(check(L, M)))
    for i in a:
        if S[check2(i, L, N)] != T[check2(i, L, M)]:
            ans = -1
            break
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import fractions
def main():
    N, M = (int(_) for _ in input().split())
    S = input()
    T = input()
    g = fractions.gcd(N, M)
    for i in range(N):
        if i % (N//g) == 0 and S[i] != T[M*i//N]:
            print(-1)
            break
    else:
        print(N * M // g)
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
import fractions
from functools import reduce
import sys
input = sys.stdin.readline


def main():
    n, m = input_list()
    s = input()
    t = input()
    baisuu = lcm_base(n, m)
    ans = {}
    for i in range(1, n+1):
        index = (i - 1) * (baisuu//n) + 1
        ans[index] = s[i-1]

    for i in range(1, m+1):
        index = (i - 1) * (baisuu//m) + 1
        w = t[i-1]
        if index in ans:
            if ans[index] != w:
                print(-1)
                exit(0)
        else:
            ans[index] = w

    print(baisuu)


def input_list():
    return list(map(int, input().split()))

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

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from fractions import gcd

N,M = map(int,input().split())
S = input()
T = input()

G = gcd(N, M)
L = N * M // G
ng = N//G
mg = M//G

for i in range(0,L,ng*mg):
    Nnum = i//mg
    Mnum = i//ng
    if S[Nnum] != T[Mnum]:
        print(-1)
        exit()

print(L)

Submission status: Accepted

Solution code:
from fractions import gcd

N,M = map(int,input().split())
S = input()
T = input()

G = gcd(N, M)
L = N * M // G
ng = N//G
mg = M//G

for i in range(G):
    Nnum = i*ng
    Mnum = i*mg
    if S[Nnum] != T[Mnum]:
        print(-1)
        exit()

print(L)

Submission status: Accepted

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

N,M = map(int,input().split())
S = input()
T = input()

if M > N:
  N,M = M,N
  S,T = T,S

X = lcm(N,M)

n = N // fractions.gcd(N,M)
m = M // fractions.gcd(N,M)

for i in range(0,X,m):
  if S[0] != T[0]:
    print(-1)
    break
  elif i % n == 0:
    s = i // n
    t = i // m
    if S[t] != T[s]:
      print(-1)
      break
else:
  print(X)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s = input()
t = input()
def gcd(a, b):
    while b!=0:
        a, b = b, a%b
    return a
g = gcd(n, m)
l = n*m//g
for i, j in zip(s[0:n:n//g], t[0:m:m//g]):
    if i!=j:
        print(-1)
        break
else:
    print(l)

Submission status: Accepted

Solution code:
import fractions
n,m = map(int,input().split())
s = input()
t = input()

lcm = n*m // fractions.gcd(n,m)
ans = -1
ss = lcm // m
ts = lcm // n
j = 0
flg = True
for i in range(0,n,ss):
    if s[i] == t[j] :
        j += ts
        continue
    else:
        flg = False
        break

if flg :
    ans = lcm
print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)
def lcm(a,b):
    return (a//gcd(a,b)*b)
n,m = map(int,readline().split())
s = readline().rstrip().decode('utf-8')
t = readline().rstrip().decode('utf-8')
l = lcm(n,m)
g = gcd(n,m)
flag = 1

for i in range((n-1)//(n//g)+1):
    if not s[i*(n//g)] == t[i*(m//g)]:
        flag = 0
        break


if flag:
    print(l)
else:
    print(-1)

Submission status: Accepted

Solution code:
import fractions
n , m = map(int,input().split())
s = input()
t = input()
l = n*m//fractions.gcd(n,m)
p = l//n
q = l//m

for i in range(10**9):
    if q*i >= n or p*i >= m:
        print(l)
        exit()
    if s[q*i] != t[p*i]:
        print(-1)
        exit()

Submission status: Accepted

Solution code:
def gcd(m,n):
    while (m % n != 0):
        n,m = m%n,n
    return(n)

def lcm(m,n):
    return(m * n // gcd(m,n))

n,m = map(int,input().split())

s = input()
t = input()


g = gcd(m,n)

if(g in [n,m]):
    print(-1)
else:
    x = lcm(m,n)
    a = x // n
    b = x // m
    for i in range(n//b):
        ai = b * i
        bi = a * i
        if(s[ai] != t[bi]):
            print(-1)
            exit()
    print(lcm(m,n))

Submission status: Accepted

Solution code:
from fractions import gcd
n,m = map(int,input().split())
l = gcd(n,m)
s = input()
t = input()
ok = True
for i in range(l):
    if s[i*n//l] != t[i*m//l]:
        ok = False
print(n*m//l if ok else '-1')

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=input()
t=input()
import fractions
x=n*m//(fractions.gcd(n,m))
n1=x//n
m1=x//m
x1=n1*m1//(fractions.gcd(n1,m1))
if n%m==0:
  for i in range(m):
    if t[i]!=s[n*i//m]:
      print("-1")
      exit()
  print(x)
  exit()
elif m%n==0:
  for i in range(n):
    if s[i]!=t[m*i//n]:
      print("-1")
      exit()
  print(x)
  exit()
else:
  for i in range(x//x1):
    if s[i*x1//n1]!=t[i*x1//m1]:
      print(-1)
      exit()
print(x)

Submission status: Accepted

Solution code:
from fractions import gcd


N, M = map(int, input().split(" "))
S = input()
T = input()
a, b = M // gcd(N, M), N // gcd(N, M)
GCD = gcd(N, M)

flag = True
for n in range(0, GCD):
    flag &= S[b * n] == T[a * n]

if flag:
    print(N * M // GCD)
else:
    print(-1)

Submission status: Accepted

Solution code:
from fractions import gcd

N,M = list(map(int, input().split()))
s = input()
t = input()

if s[0] != t[0]:
    print(-1)
    exit()
if s == t:
    print(N)
    exit()

saisho_kobaisu = (N * M) // gcd(N, M)
# print(saisho_kobaisu)

s_d = saisho_kobaisu // N
t_d = saisho_kobaisu // M

s_set = set([i * s_d + 1 for i in range(N)])
t_set = set([i * t_d + 1 for i in range(M)])

# print(s_set)
# print(t_set)
# print(s_set.intersection(t_set))
for idx in s_set.intersection(t_set):
    if (idx-1)//s_d > N or (idx-1)//t_d > M:
        break
    if s[(idx-1)//s_d] != t[(idx-1)//t_d]:
        print(-1)
        exit()

print(saisho_kobaisu)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n, m = map(int, input().split())
s = input() #sys.stdin.readlineは最後が改行
t = input() #sys.stdin.readlineは最後が改行

from fractions import gcd

gcdnm = gcd(n, m)
L = (n * m) // gcdnm

gcdd = gcd(L//n, L//m)
l = (L//n *L//m) // gcdd


if s[0]!=t[0]:
    print(-1)
    exit()

i = 1


while l//(L//n)*i < n and l//(L//m)*i <m:
    if s[l//(L//n)*i] != t[l//(L//m)*i]:
        print(-1)
        exit()
    i+=1

print(L)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=list(input())
t=list(input())
import fractions
x=n*m//fractions.gcd(n,m)
s_lis=[i*x//n+1 for i in range(n)]
t_lis=[i*x//m+1 for i in range(m)]
import bisect
for i in range(n):
    ind=bisect.bisect_left(t_lis,s_lis[i])
    if ind==m:
        continue
    if t_lis[ind]==s_lis[i]:
        if s[i]!=t[ind]:
            print(-1)
            exit()

print(x)

Submission status: Accepted

Solution code:
from fractions import gcd
N, M = map(int, input().split())
S = input()
T = input()
GCD = gcd(N, M)
LCM = N*M // gcd(N, M)
# print(GCD, LCM)
ok = True
for i in range(GCD):
    # print(i*N//GCD, i*M//GCD)
    if S[i*(N//GCD)] != T[i*(M//GCD)]:
        ok = False

if ok:
    print(LCM)
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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


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


def resolve():
    n, m = map(int, input().split())
    s = input()
    t = input()

    L = lcm(n, m)

    X = dict()
    for i in range(n):
        idx = (L // n) * i
        X[idx] = s[i]

    for i in range(m):
        idx = (L // m) * i
        if X.get(idx) != None and X[idx] != t[i]:
            print("-1")
            break
    else:
        print(L)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
S = input()
T = input()

from fractions import gcd

def solve(N,M,S,T):
    g = gcd(N,M)
    for i in range(g):
        if S[N//g*i]!=T[M//g*i]:
            return -1
    ans = N*M//g
    return ans
print(solve(N,M,S,T))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
S = input()
T = input()
from fractions import gcd

g = gcd(N, M)
flag = True
for k in range(g):
  if S[k * N // g] != T[k * M // g]:
    flag = False

if flag:
  print(N * M // g)
else:
  print(-1)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
S = input()
T = input()
from fractions import gcd

g = gcd(N, M)
flag = True
for k in range(g):
  if S[k * N // g] != T[k * M // g]:
    flag = False

if flag:
  print(N // g * M)
else:
  print(-1)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
s = input()
t = input()

from fractions import gcd
g = gcd(n,m)
ans = n*m//g

for i in range(g):
    if s[i*n//g]!=t[i*m//g]:
        ans = -1

print(ans)

Submission status: Accepted

Solution code:
import fractions

N,M = map(int,input().split())
S = input()
T = input()
L = fractions.gcd(N,M)
ans = N*M//L

if L == 1:
  print(ans) if S[0] == T[0] else print(-1)
else:
  print(ans) if S[::N//L] == T[::M//L] else print(-1)

Submission status: Accepted

Solution code:
from fractions import gcd
n,m = map(int, input().split())
s = input()
t = input()
# Xの長さLはnとmで割り切れる
# Xの1, L/n + 1, ..., (n-1) * L/n + 1 番目の文字をつなげるとSになる
# Xの1, L/m + 1, ..., (m-1) * L/m + 1 番目の文字をつなげるとTになる

ans = -1
if n==m:
    if s==t: ans= n
else:
    gcd_nm = gcd(n,m)
    for i in range(gcd_nm):
        if s[n//gcd_nm*i] != t[m//gcd_nm*i]: break
    else: ans = n*m//gcd_nm
print(ans)