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:
import fractions

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)
ST_idx = set([i*(L//N) for i in range(N)]) & set([i*(L//M) for i in range(M)])

for x in ST_idx:
    if S[(N*x)//L] != T[(M*x)//L]:
        print(-1)
        break
else:
    print(L)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
import fractions
def main():
    n,m=map(int,input().split())
    s=input()
    t=input()
    ans=-1
    if n==m:
        if s==t:
            ans=n
    else:
        gcd_nm=fractions.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)

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

n2,m2 = l//n,l//m
g2 = gcd(n2,m2)
l2 = n2*m2//g2

ans = l
for i in range(l//l2):
  if s[i*l2//n2] != t[i*l2//m2]:
    ans = -1
    break
print(ans)

Submission status: Accepted

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
#from itertools import combinations # (string,3) 3回
#from collections import deque
#import collections.defaultdict
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    n,m = readInts()
    s = input()
    t = input()
    from fractions import gcd
    g = gcd(n,m)
    res = n // g * m
    # 互いに素なn,mを作成する
    n //= g
    m //= g
    ok = True
    for i in range(g):
        # 0 ~ (g-1)まで調べる
        if s[i*n] != t[i*m]:
            ok = False
    if ok:
        print(res)
    else:
        print(-1)
if __name__ == '__main__':
  main()

Submission status: Accepted

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


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

s1=input()

s2=input()

len_moji = lcm(n,m)

len_s1 = []

len_s2 = []

for i in range(n):
    len_s1.append(i*len_moji//n+1)

for i in range(m):
    len_s2.append(i*len_moji//m+1)
#print(len_s1)
#print(len_s2)
count = 0
for ix, vs1 in enumerate(len_s1):
    for jx in range(count,len(len_s2)):
        #print(vs1, len_s2[jx])
        if vs1 < len_s2[jx]:
            count = jx-1
            break
        if vs1 == len_s2[jx]:
            count = jx
            if s1[ix] != s2[jx]:
                print(-1)
                exit()
            break
print(len_moji)

Submission status: Accepted

Solution code:
# python3.4.2用
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from decimal import *
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') #無限大
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(sys.stdin.readline()) #整数読み込み
def ifn(): return float(sys.stdin.readline()) #浮動小数点読み込み
def isn(): return sys.stdin.readline().split() #文字列読み込み
def imn(): return map(int, sys.stdin.readline().split()) #整数map取得
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) #整数-1map取得
def fmn(): return map(float, sys.stdin.readline().split()) #浮動小数点map取得
def iln(): return list(map(int, sys.stdin.readline().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, sys.stdin.readline().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD
def lprint(l): print(*l, sep='\n')
def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime


N,M = imn()
S = input()
T = input()

L = lcm(N,M)
g = gcd(N,M)

is_good = True
for i in range(L):
    s_index = i*N//g
    t_index = i*M//g
    if s_index >= N or t_index >= M: break
    if S[s_index] != T[t_index]:
        is_good = False
        break

print(L if is_good else -1)

Submission status: Accepted

Solution code:
import fractions
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import string
import sys

sys.setrecursionlimit(10 ** 5 + 10)


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


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

        lcm = N * M // fractions.gcd(N, M)
        NN = lcm // N
        MM = lcm // M

        lcm2 = NN * MM // fractions.gcd(NN, MM)
        i = 0
        ans = lcm
        while True:
            if lcm2 * i // NN < N and lcm2 * i // MM < M:
                if S[lcm2 * i // NN] != T[lcm2 * i // MM]:
                    ans = -1
                i += 1
            else:
                return ans

    print(main())


resolve()

Submission status: Accepted

Solution code:
import fractions
def main():
    n,m=map(int,input().split())
    s=input()
    t=input()
    ans=-1
    gcd0=fractions.gcd(n,m)
    lcm=n*m//gcd0
    flg=1
    for i in range(gcd0):
        if s[n*i//gcd0]!=t[m*i//gcd0]:
            flg=0
            break
    if flg==1:
        ans=lcm
    print(ans)
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s, t = [input() for i in range(2)]

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

a = len(s)
b = len(t)

g = gcd(a, b)

if all([s[a*i//g]==t[b*i//g] for i in range(g)]):
    print(a*b//g)
else:
    print(-1)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=input()
t=input()
import fractions
g=fractions.gcd(n,m)
m0=m//g
n0=n//g
i=0
while i*n0<n and i*m0<m:
  if s[i*n0]==t[i*m0]:
    pass
  else:
    print(-1)
    exit()
  i+=1
print(n*m//g)

Submission status: Accepted

Solution code:
from fractions import gcd

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

r = gcd(N, M)
n = N // r
m = M // r

ans = -1
if S[0] != T[0]:
    print(ans)
    exit(0)

X = {}
for i, s in enumerate(S[1:]):
    idx = (i + 1) * m + 1
    X[idx] = s
    ans = max(ans, idx)

for i, t in enumerate(T[1:]):
    idx = (i + 1) * n + 1
    if (idx in X) and (X[idx] != t):
        print(-1)
        exit(0)
    else:
        ans = max(ans, idx)

print(max(ans, r * m * n))

Submission status: Accepted

Solution code:
from fractions import gcd
n,m = [int(x) for x in input().split()]
s = input()
t = input()

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

ans = f(n,m)

if s[::ans//m] == t[::ans//n]:
    print(ans)
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)
if S[::L//M]==T[::L//N]:
  print(L)
else:
  print(-1)

Submission status: Accepted

Solution code:
from fractions import gcd
N,M=map(int,input().split())
S=input()
T=input()
L=N*M//gcd(N,M)
p=[]
q=[]

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

Submission status: Accepted

Solution code:
from fractions import gcd
N,M=map(int,input().split())
S=input()
T=input()
L=N*M//gcd(N,M)
p=[]
q=[]

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

Submission status: Accepted

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

Submission status: Accepted

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

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

l=lcm(n, m)
index=fractions.gcd(n,m)
#print(indexn,indexm)
for i in range(index):
    #print(i)
    if s[n//index*i]!=t[m//index*i]:
        print(-1)
        break
else:
    print(l)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from fractions import gcd
n, m = map(int, input().split())
s = input()
t = input()
#一文字目が違うと無理
gcd_n_m = gcd(n,m)
if gcd_n_m == 1 and s[0] == t[0]:
    print(n*m)
else:
    step_s = n // gcd_n_m
    step_t = m // gcd_n_m
    index_s = 0
    index_t = 0
    while index_s < n and index_t < m:
        if s[index_s] != t[index_t]:
            print(-1)
            exit()
        index_s += step_s
        index_t += step_t
    print(n*m//gcd_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)
n=N//g
m=M//g
s=[]
t=[]
for i in range(N):
    if i%n==0:
        s.append(S[i])
for j in range(M):
    if j%m==0:
        t.append(T[j])
for x,y in zip(s,t):
    if x!=y:
        print(-1)
        exit()
print(M*N//g)

Submission status: Accepted

Solution code:
import sys
from fractions import gcd


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


sys.setrecursionlimit(10 ** 9)


def main():
    N, M = map(int, input().split())
    S = input()
    T = input()
    g = gcd(M, N)
    n = N // g
    m = M // g
    s = []
    t = []
    for i in range(N):
        if i % n == 0:
            s.append(S[i])
    for j in range(M):
        if j % m == 0:
            t.append(T[j])
    for x, y in zip(s, t):
        if x != y:
            print(-1)
            return
    print(M * N // g)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

L = lcm(N, M)
num = lcm(L//N, L//M)

n = (N-1)*(L//N)+1
m = (M-1)*(L//M)+1

if(max(n, m) < num):
    if(S[0] == T[0]):
        print(L)
    else:
        print(-1)
else:
    if(N > M):
        tmp = M//(L//N)
    else:
        tmp = N//(L//M)
    for i in range(tmp):
        if(S[i*L//M] != T[i*L//N]):
            print(-1)
            break
    else:
        print(L)

Submission status: Accepted

Solution code:
import fractions
import sys
from sys import stdin

n, m = map(int, stdin.readline().rstrip().split())
s = stdin.readline().rstrip()
t = stdin.readline().rstrip()


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


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

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
S = input()
T = input()
L = N*M//gcd(N, M)
g = gcd(N, M)
for i in range(g):
	if S[N//g*i] != T[M//g*i]:
		print(-1)
		break
else:
	print(L)

Submission status: Accepted

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

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

n, m = map(int, input().split())
s = list(input())
t = list(input())
g = gcd(n, m)
l = lcm(n, m)
x_s = [i for i in range(1, l + 1, m // g)]
x_t = [i for i in range(1, l + 1, n // g)]
j = 0
c = 1
for i in range(len(x_s)):
    while True:
        if j + 1 == len(x_t):
            break
        if x_s[i] > x_t[j]:
            j += 1
        else:
            break
    if x_s[i] == x_t[j]:
        if not s[i] == t[j]:
            c = 0
print(l if c == 1 else -1)

Submission status: Accepted

Solution code:
from fractions import gcd

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

gc = gcd(N, M)

ans = N*M//gc

for i in range(gc):
    if S[N//gc*i] != T[M//gc*i]:
        ans = -1
        break
                
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
N,M=map(int,input().split())
S=list(input())
T=list(input())
L=gcd(N,M)
print(N*M//L if all([S[i*N//L]==T[i*M//L] for i in range(L)]) 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)
lcm = N * M // g
for i in range(g):
  if S[i*N//g] != T[i*M//g]:
    print(-1)
    exit()
print(lcm)

Submission status: Accepted

Solution code:
from collections import defaultdict
from fractions import gcd
N, M = map(int, input().split())
S = input()
T = input()
L = N * M // gcd(N, M)
ds = L // N
dt = L // M
dict_s = defaultdict(str)
dict_t = defaultdict(str)

for i in range(N):
  dict_s[i*ds] = S[i]
  
for i in range(M):
  dict_t[i*dt] = T[i]

for key in dict_s.keys():
  if key in dict_t.keys():
    if dict_s[key] != dict_t[key]:
      print(-1)
      exit()
print(L)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
S=input()
T=input()
from fractions import gcd
g=gcd(N,M)
L=N*M//g
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:
# たぶん最小の値は最小公倍数になりそう
# 内包表記 -> TLE
# [0]*l -> RE

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


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


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


l = lcm(n, m)
arr = {}

for i in range(n):
    x = i * (l // n)
    arr[x] = s[i]

for i in range(m):
    x = i * (l // m)
    if x in arr and arr[x] != 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()
g = gcd(n,m)
ng = n//g
mg = m//g
for i in range(g):
    if s[ng*i]!=t[mg*i]:
        print("-1")
        break
else:
    print(n*m//g)

Submission status: Accepted

Solution code:
def main():
    from fractions import gcd

    n, m = map(int, input().split())
    s, t = input(), input()
    l = n * m // gcd(n, m)
    a = [l // n * i + 1 for i in range(n)]
    b = [l // m * i + 1 for i in range(m)]
    c = set(a) & set(b)
    for x in list(c):
        i = a.index(x)
        j = b.index(x)

        if s[i] != t[j]:
            print(-1)
            exit()
    else:
        print(l)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import fractions


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

def check():
    N, M = map(int, input().split())
    S = input()
    T = input()
    length = lcm(N,M)
        
    for i in [a*(length//N) for a in range(N)]:
        if i%(length//M)==0:
            if S[i//(length//N)] != T[i//(length//M)]:
                return -1
    return length
  
print(check())

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

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

def solve():
    N,M = map(int, input().split())
    S = input()
    T = input()
    gcd_NM = gcd(N,M)
    lcm_NM = (N*M)//gcd_NM
    S_diff = N // gcd_NM
    T_diff = M // gcd_NM
    
    i = 0
    possible = True
    while S_diff*i < N and T_diff*i < M:
        if S[S_diff*i] != T[T_diff*i]:
            possible = False
        i += 1
        
    print(lcm_NM if possible else -1)
    
solve()

Submission status: Accepted

Solution code:
from fractions import gcd

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

lcm = N * M // gcd(N, M)
n = N // gcd(N, M)
m = M // gcd(N, M)

for k in range(gcd(N, M)):
    a = k * n
    b = k * m
    if S[a] != T[b]:
        print(-1)
        exit()

print(lcm)

Submission status: Accepted

Solution code:
from fractions import gcd

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


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


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

for i in range(gcd(N, M)):
    if S[i * n] != T[i * m]:
        print("-1")
        break
else:
    print(lcm(N, M))

Submission status: Accepted

Solution code:
import fractions
N,M=map(int,input().split())
S=input()
T=input()
lcm=(N*M)/fractions.gcd(N,M)
num=0
s=[]
t=[]
flag=1
sindex=0
tindex=0
while (sindex<N)and(tindex<M):
    if S[sindex]!=T[tindex]:
        flag=0
        break
    sindex=sindex+(N//fractions.gcd(N,M))
    tindex = tindex + (M // fractions.gcd(N, M))
"""
for j in range(N):
    s.append([S[j],int(1+(num//N)*j)-1])
for j in range(M):
    t.append([T[j], int(1 + (num // M) * j) - 1])
#print(s,t)
while (sindex<N)and(tindex<M):
    #print(sindex,tindex)
    if s[sindex][1]==t[tindex][1]:
        if s[sindex][0]!=t[tindex][0]:
            flag=0
            break
        sindex=sindex+1
        tindex=tindex+1
    elif s[sindex][1]<t[tindex][1]:
        sindex=sindex+1
    else:
        tindex = tindex + 1
    #input()
"""
if flag==0:
    print("-1")
else:
    print(int(lcm))

Submission status: Accepted

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

from fractions import gcd
def lcm(a):
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

long=lcm([n,m])

ln=int(long/n)
lm=int(long/m)

#ans=[]

ok=True

for i in range(n-1):
    if (i*ln)%lm==0:
        if s[i]!=t[(i*ln)//lm]:
            ok=False

if n==1:
    if s!=t[0]:ok=False
if m==1:
    if t!=s[0]:ok=False

if not ok:long=-1

print(long)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s = input()
t = input()
def gcd(a, b):
    if b == 0: return a
    if a < b: a, b = b, a
    return gcd(b, a%b)
def lcm(a, b):
    return a*b//gcd(a, b)
x = ""
nm = lcm(n, m)
N = {}
M = {}
for i in range(n):
    N[(nm//n)*i] = s[i]
for i in range(m):
    M[(nm//m)*i] = t[i]
if n > m:
    n, m = m, n
    N, M = M, N
f = True
g = lcm(nm//n, nm//m)
for i in N.keys():
    if i % g == 0:
        if N[i] != M[i]:
            f = False
if f: print(nm)
else: print(-1)

Submission status: Accepted

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

#a,bの最大公約数
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#a,bの最小公倍数
def lcm(a, b):
    return a * b // gcd (a, b)
#%%
# L は N, Mの最小公倍数
L = lcm(N, M)

# 文字が一致しなければならないindexは公倍数で、L//MとL//Nが入れ替わる
if S[::L//M] == T[::L//N]:
    print(L)
else:
    print(-1)

Submission status: Accepted

Solution code:
from fractions import gcd


def main():
    s_length, t_length = map(int, input().split())
    s = input()
    t = input()
    lcm = s_length * t_length // gcd(s_length, t_length)
    answer = True
    for i in range(s_length):
        if (i * t_length) % s_length == 0 and s[i] != t[(i * t_length) // s_length]:
            answer = False
            break
    print(lcm if answer else -1)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

## 最小公倍数(LCM)
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

def solve(N: int, M: int, S: str, T: str):
    X = lcm(N,M)
    i = j = 0

    while i < N and j < M:
        if S[i] == T[j]:
            i += X//M
            j += X//N
            continue
        else:
            print(-1)
            return
    print(X)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    T = next(tokens)  # type: str
    solve(N, M, S, T)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import fractions


def binary_search(list, number, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) // 2
        guess = list[mid][0]
        if guess == number:
            if list[mid][1] == item:
                return False
            else:
                return True
        if guess > number:
            high = mid - 1
        else:
            low = mid + 1
    # 見つからなかったとき
    return False


n, m = map(int, input().split())
s = input()
t = input()
check = []
l = n * m // fractions.gcd(n, m)
for i in range(n):
    check.append([i * l // n, s[i]])
for i in range(m):
    if binary_search(check, i * l // m, t[i]):
        print(-1)
        exit()
print(l)

Submission status: Accepted

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

Submission status: Accepted

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

def lcd(n, m):
    # 最大公約数
    a = max(n,m)
    b = min(n,m)
    while b:
        a, b = b, a % b
    return n*m//a

l = lcd(n,m)
m1 = l//m
n1 = l//n

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

Submission status: Accepted

Solution code:
def main():
  n, m = input_list()
  s = input()
  t = input()
  gcm = fractions.gcd(n, m)
  lcm = (n*m)//gcm
  ng = n//gcm
  mg = m//gcm
  for i in range(gcm):
    if s[ng*i] != t[mg*i]:
      print(-1)
      exit(0)
  print(lcm)
  
def input_list():
  return list(map(int, input().split()))

def input_list_str():
  return map(str, 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)

# 2で割り切れる回数
def divide_two(arg):
  c = 0
  while True:
    if c >= 2:
      break
    if arg % 2 != 0:
      break
    arg //= 2
    c += 1
  return c 

import math
import fractions
import collections
from functools import reduce
main()

Submission status: Accepted

Solution code:
import fractions
N,M=map(int,input().split())
S=input()
T=input()
g=fractions.gcd(N,M);l=N*M//g
if(g==1):
    print(l if S[0]==T[0] else -1)
    exit()
a,b=0,0
n=N//g;m=M//g
while(a<N and b<M):
    if(S[a]!=T[b]):
        print(-1)
        exit()
    a+=n;b+=m
print(l)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import defaultdict
from fractions import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)

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

"""
存在するならば長さは必ずLである。
Lで存在しない場合、n * Lでも存在しない
"""
L = lcm(N, M)

X = defaultdict(str)

for p,s in enumerate(S):
    X[p * L // N] = s

flag = True
for q,t in enumerate(T):
    if X[q * L // M] and X[q * L // M] != t:
        flag = False
    else:
        X[q * L // M] = t

ans = L if flag else -1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from fractions import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)

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

L = lcm(N, M)

X = defaultdict(str)

for p,s in enumerate(S):
    X[p * L // N] = s

flag = True
for q,t in enumerate(T):
    if X[q * L // M] and X[q * L // M] != t:
        flag = False
    else:
        X[q * L // M] = t

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

Submission status: Accepted

Solution code:
a,s=map(int,input().split())
sa,ss=[input() for i in range(2)]
if a<s:
    a,s=s,a
    sa,ss=ss,sa
from fractions import gcd
g=gcd(a,s)
x,y=a//g,s//g
for i in range(g):
    if sa[x*i]!=ss[y*i]:print(-1);break
else:print(x*s)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys

N,M = list(map(int, input().rstrip().split()))
S = input().strip()
T = input().strip()
#-----

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

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

lcm = lcm(N,M)
L = lcm
X1_dic={}

X1_dic[0] = S[0]
for i in range(1,N):
    X1_dic[ int(i*(L/N)+1) - 1 ] = S[i]


if X1_dic[0] != T[0]:
    print(-1)
    sys.exit()

for i in range(1,M):
    key = int(i*(L/M)+1) - 1
    if (key in X1_dic) and  X1_dic[key] != T[i]:
        print(-1)
        sys.exit()
    
print(L)

Submission status: Accepted

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

from fractions import gcd
L = N * M // gcd(N, M)
step_s = L // M
step_t = L // N
stop = N // step_s
flag = True

for i in range(stop):
  #print(i, S[i * step_s], T[i * step_t])
  if S[i * step_s] != T[i * step_t]:
    flag = False
    break

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

Submission status: Accepted

Solution code:
from fractions import gcd

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

L = (N * M) // gcd(N, M)

L1 = [0]
L2 = [0]

from collections import Counter
c = Counter()

for i in range(1, N):
    t = i * (L // N) + 1
    L1.append(t-1)

for i in range(1, M):
    t = i * (L // M) + 1
    L2.append(t-1)


d = {}
for i, li in enumerate(L1):
    d[li] = S[i]

# print(d)

ans = True

for i, li in enumerate(L2):
    if not d.get(li):
        continue
    if d[li] != T[i]:
        ans = False

# print(L1)
# print(L2)
# print(common)
# print(dic)

if ans:
    print(L)
else:
    print(-1)

Submission status: Accepted

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

def gcd(a, b):
    if a < b:
        a, b = b, a

    if b == 0:
        return a

    else:
        return gcd(b, a - b)

lcm = N * M // gcd(N, M)
s_c_dict = dict([[j, S[i]] for i, j in enumerate(range(0, lcm, lcm//N))])
for i, j in enumerate(range(0, lcm, lcm//M)):
    if j in s_c_dict:
        if s_c_dict[j] != T[i]:
            print(-1)
            exit()
print(lcm)

Submission status: Accepted

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

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

for i in range(g):
    if S[i*n]!=T[i*m]:
        judge=False

if judge==True:
    print(N*M//g)
else:
    print(-1)

Submission status: Accepted

Solution code:
from fractions import gcd

def main():
    n, m = map(int, input().split())
    s = input().rstrip()
    t = input().rstrip()
    l = n*m // gcd(n, m)
    f = True
    for i in range(n):
        if i*m//n * n == i*m:
            j = i*m//n
            if s[i] != t[j]:
                f = False
    if f:
        print(l)
    else:
        print("-1")

if __name__ == "__main__":
    main()

Submission status: Accepted

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

n, m = map(int, input().split())
s = input()
t = input()
d = dict()
f = True

g = lcm(n, m)
nn = g // n
mm = g // m

for i in range(n):
    d[1 + nn * i] = s[i]

for i in range(m):
    if 1+mm*i in d:
        if d[1+mm * i] != t[i]:
            f = False
if f:
    print(g)
else:
    print(-1)

Submission status: Accepted

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

Submission status: Accepted

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

# import math
import fractions
gcdd = fractions.gcd(n, m)

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

print(n*m//gcdd)

Submission status: Accepted

Solution code:
#028_A
from fractions import gcd

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

g=gcd(N,M)
n,m=N//g,M//g

for k in range(0,g):
    if S[k*n]!=T[k*m]:
        flg=False

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

Submission status: Accepted

Solution code:
import fractions

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

gcd = fractions.gcd(n,m)

print(n*m//gcd if all([s[i*n//gcd]==t[i*m//gcd] for i in range(gcd)]) else -1)

Submission status: Accepted

Solution code:
import fractions
N, M = map(int, input().split())
S = input()
T = input()
f = fractions.gcd(N, M)
flag = True
for i in range(f):
    if S[i*N//f] != T[i*M//f]:
        flag = False
        break
print([-1,N*M//f][flag])

Submission status: Accepted

Solution code:
from fractions import gcd
lcm=lambda x,y:x//gcd(x,y)*y
N,M=map(int, input().split())
S=input()
T=input()
g=gcd(N,M)
if all(S[N//g*i]==T[M//g*i] for i in range(g)):
    print(lcm(N,M))
else:
    print(-1)

Submission status: Accepted

Solution code:
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
def lcm(a, b):
	return a * b // gcd (a, b)
 
n,m = map(int,input().split())
s = input()
t = input()

l = lcm(n,m)
gaps = l//m
gapt = l//n

i,j = 0,0
while i<n:
    if s[i]!=t[j]:
        print(-1)
        break
    else:
        i += gaps
        j += gapt
else:
    print(l)