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 sys
N, M = [int(i) for i in input().split(' ')]
S, = [i for i in input().split(' ')]
T, = [i for i in input().split(' ')]
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

if S[0] != T[0]:
    print(-1)
else:
    x = lcm(N,M)
    a = x // N
    b = x // M
    c = lcm(a, b)
    ii = 1
    while ii * c + 1 <= x:
#        print(S[ii * (c//a)])
#        print(T[ii * (c//b)])
        if S[ii * (c//a) ] != T[ii * (c//b) ]:
            print(-1)
            sys.exit()
        ii += 1
    print(x)

Submission status: Accepted

Solution code:
import fractions

N, M = (int(i) for i in input().split())  
S = input()
T = input()

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

flag = True
for i in range(L):
    if (S[N//L * i] != T[M//L * i]):
        flag = False

if flag:
    print(lcm)
else:
    print("-1")

Submission status: Accepted

Solution code:
def gcd(N,M):
    while True:
        if min(N,M)==0:
            return max(N,M)
        elif N>=M:
            N%=M
        elif M>N:
            M%=N
def lcm(N,M):
    return N*M//gcd(N,M)

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

L=lcm(N,M)

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

Submission status: Accepted

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

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

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

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

for k in range(l//(nn*mm)):
    if s[k*nn] != t[k*mm]:
        print(-1)
        break
else:
    print(l)

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

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

L = lcm(N,M)
G = gcd(N,M)
n = L//N
m = L//M

s = [S[i*m] for i in range(G)]
t = [T[i*n] for i in range(G)]

if s == t or (G == 1 and S[0]==T[0]):
    print(L)
else:
    print(-1)

Submission status: Accepted

Solution code:
# coding:utf-8

import sys


input = sys.stdin.readline
INF = float('inf')


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


# 整数(x, y)最大公約数を求める
def gcd(x, y):
    if x % y == 0:
        return y
    else:
        x, y = y, x % y
        return gcd(x, y)


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


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

L = lcm(N, M)
LCM = lcm(L//N, L//M)
# print(L, LCM)

ss = L // N
cnt = 0
tmp = 0
S_li = [S[0]]
while tmp <= L:
    tmp = ss * cnt + 1
    if tmp % LCM == 1:
        S_li.append(S[cnt])
    cnt += 1

tt = L // M
cnt = 0
tmp = 0
T_li = [T[0]]
while tmp < L:
    tmp = tt * cnt + 1
    if tmp % LCM == 1:
        T_li.append(T[cnt])
    cnt += 1

# print(S_li)
# print(T_li)
if S_li == T_li:
    print(L)
else:
    print(-1)

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

gcd = _gcd(N,M)
lcm = N*M//gcd

def check():
  a,b = 0,0
  da,db = N//gcd, M//gcd
  while a < N:
    if S[a]!=T[b]:
      print(-1)
      return
    a+=da
    b+=db
  print(lcm)

check()

Submission status: Accepted

Solution code:
import fractions


def main():
    n, m = map(int, input().split())
    s = input()
    t = input()
    l = n * m // fractions.gcd(n, m)
    x = {}
    for i in range(n):
        x[i * (l // n)] = s[i]
    for i in range(m):
        if i * (l // m) not in x:
            continue
        if x[i * (l // m)] != t[i]:
            print(-1)
            return
    print(l)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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



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

MA = [S[0]]
NA = [T[0]]

L = lcm(M, N)

m = L/M
n = L/N

for i in range(M):
    if i % n == 0:
        MA.append(S[i])

for i in range(N):
    if i % m == 0:
        NA.append(T[i])

if MA == NA:
    print(L)
else:
    print("-1")

Submission status: Accepted

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

Submission status: Accepted

Solution code:
l = raw_input().split()

N = int(l[0])
M = int(l[1])

strA = raw_input()
strB = raw_input()


#nmgcd = math.gcd(N,M)
nmgcd = N
eu = M

while eu:
	nmgcd, eu = eu, nmgcd % eu


nmlcm = (N*M)//nmgcd




itr = 0

for i in range(nmgcd):
    if strA[0+i*(nmlcm//M)] == strB[0+i*(nmlcm//N)]:
        itr = itr +1

if itr == nmgcd:
    print(nmlcm)
else:
    print(-1)

Submission status: Accepted

Solution code:
import fractions

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

l = n * m // fractions.gcd(n, m)
ans = l
dic = {}
for i in range(n):
    j = (l // n) * i % l
    if j in dic and dic[j] != s[i]:
        ans = -1
        break
    dic[j] = s[i]
for i in range(m):
    j = (l // m) * i % l
    if j in dic and dic[j] != t[i]:
        ans = -1
        break
    dic[j] = t[i]
print(ans)

Submission status: Accepted

Solution code:
import fractions


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


n, m = [int(_) for _ in input().split()]
s = input()
t = input()
a = lcm(n, m)
s_a = a // n
t_a = a // m
p = lcm(s_a, t_a)
result = True
for i in range(a//p):
    if s[(i*p)//s_a] != t[(i*p)//t_a]:
        result = False
if result:
    print(a)
else:
    print(-1)

Submission status: Accepted

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

nm = input().split()
n = int(nm[0])
m = int(nm[1])
s = input()
t = input()
g = gcd(m,n)

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

Submission status: Accepted

Solution code:
import numpy as np
import scipy
def gcd(a, b):
    if a % b:
        return gcd(b, (a % b))
    else:
        return b
N, M = map(int,input().split())
S = input()
T = input()
t = gcd(N,M)
n = N // t
m = M // t
ans = n * m * t
for i in range(t):
    if(S[n*i]!=T[m*i]):
        ans = -1
        break
print(ans)

Submission status: Accepted

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

L = int(N * M / fractions.gcd(N, M))
LN = int(L / N)
LM = int(L / M)

count = 0
dic1 = {LN*n:S[n] for n in range(N)}
dic2 = {LM*n:T[n] for n in range(M)}

for k in dic1.keys():
    if k in dic2 and dic1[k] != dic2[k]:
        count += 1
        print(-1)
        break

if count == 0:
    print(L)

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 = gcd(N,M)

d = M * (N // c)

a1 = d // N
a2 = d // M

#print(a1,a2)
for i in range(min(N//a2,M//a1)):
    if S[a2*i] != T[a1*i]:
        print(-1)
        exit()

print(d)

Submission status: Accepted

Solution code:
def lcm(a, b):
    small = min(a, b)
    large = max(a, b)
    gcd = small
    while large % small != 0:
        tmp = small
        small = large % small
        large = tmp
        gcd = small

    return(a * b // gcd)


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

lcm_nm = lcm(N, M)
s_base = lcm_nm // M
t_base = lcm_nm // N
i = 0
while s_base * i < N and t_base * i < M:
    if S[i * s_base] != T[i * t_base]:
        print(-1)
        exit()
    i += 1

print(lcm_nm)

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()
jn = 0
jm = 0
l = lcm(n,m)
ln = l // n
lm = l // m
d = lcm(ln, lm)
for i in range(0, l, d):
    if S[i // ln] != T[i // lm]:
        print(-1)
        exit()
print(l)

Submission status: Accepted

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


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


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

l = lcm(n, m)
g = gcd(n, m)

ng = n // g
mg = m // g
k = 0
flg = True
while True:
    if k * ng >= n or k * mg >= m:
        break
    if s[k * ng] != t[k * mg]:
        flg = False
        break
    k += 1

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

Submission status: Accepted

Solution code:
# 最小公倍数
# ユークリッドの互除法
def lcm(a, b): 
    def gcd(a, b):  # a >= b
        if b == 0:
            return a
        else:
            return gcd(b, a % b)
    
    return a * b // gcd(a, b)

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

l = lcm(N, M)

ans = {}
flag = True

for i in range(N):
    now = (l // N) * i + 1
    ans[now] = S[i]

for i in range(M):
    now = (l // M) * i + 1
    if now in ans:
        if ans[now] != T[i]:
            flag = False
            break

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

Submission status: Accepted

Solution code:
import fractions


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


def solve(n, m, s, t):
    le = lcm(n, m)
    s_new_ps = {le // n * i for i in range(n)}
    t_new_ps = {le // m * i for i in range(m)}
    conf_new_ps = s_new_ps & t_new_ps
    for p in conf_new_ps:
        i = p // (le // n)
        j = p // (le // m)
        if s[i] != t[j]:
            return None
    return le


def main():
    n, m = (int(z) for z in input().split())
    s = input()
    t = input()
    res = solve(n, m, s, t)
    if res is None:
        print(-1)
    else:
        print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

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

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


N, M = map(int,input().split(' '))
S = input()
T = input()
L = lcm([N,M])
L_N = L // N
L_M = L // M
nowN = 0
nowM = 0
countN = 0
countM = 0
while True:
#    print(nowN,nowM)    
#    print(countN,countM)
    if nowN < nowM:
        nowN += L_N
        countN +=1
    elif nowM < nowN:
        nowM += L_M
        countM +=1
    elif nowM == nowN:
#        print(S[countN])
#        print(T[countM])
        if S[countN] != T[countM]:
            print('-1') 
            exit()
        else:
            countN +=1
            nowN += L_N
    if nowN >= L and nowM >= L:
        print(str(L))
        exit()

Submission status: Accepted

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

def gcd(m,n):
    x = max(m,n)
    y = min(m,n)
    if x%y == 0:
        return y
    else:
        while x%y != 0:
            z = x%y
            x = y
            y = z
        else:
            return z

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

d = gcd(N,M)
l = lcm(N,M)

s = [0 for i in range(0,d)]
t = [0 for i in range(0,d)]

a = int(l/M)
b = int(l/N)

for i in range(0,d):
    s[i] = S[i*a]
    t[i] = T[i*b]

if s == t:
    print(l)
else:
    print(-1)

Submission status: Accepted

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


for i in range(n):
  if int(i*a)%b==0:
    if s[i]==t[int(i*a/b)]:c+=1
    else:
      break
if c==(int(lcm(n,m)/lcm(a,b))):print(lcm(n,m))
else:print(-1)

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

LCM = lcm(N,M)
GCD = gcd(N,M)

for i in range(0,LCM,LCM//GCD):
    if S[i*N//LCM] != T[i*M//LCM]:
        print(-1)
        exit()
print(LCM)

Submission status: Accepted

Solution code:
def gcd(x, y):
    if x == 0:
        return y
    elif y == 0:
        return x
    elif x % 2 == 0 and y % 2 == 0:
        return 2 * gcd(x//2, y//2)
    elif x % 2 == 0:
        return gcd(x//2, y)
    elif y % 2 == 0:
        return gcd(x, y//2)
    elif y >= x:
        return gcd(x, (y-x)//2)
    else:
        return gcd((x-y)//2, y)


n, m = tuple(map(int, input().split()))
s = list(input())
t = list(input())
g = gcd(n, m)
ng = n // g
mg = m // g
res = n * m // g
for i in range(0, g):
    if s[ng * i] != t[mg * i]:
        res = -1
        break

print(res)

Submission status: Accepted

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


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

sl = [i for i in range(0, N, N//gcd)]
tl = [i for i in range(0, M, M//gcd)]
for i in range(len(sl)):
    if S[sl[i]] != T[tl[i]]:
        print(-1)
        break
else:
    print(N*M//gcd)

Submission status: Accepted

Solution code:
# coding: utf-8

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())

l = lcm(N,M)

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

Submission status: Accepted

Solution code:
import fractions

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


N, M = [int(i) for i in input().split()]
s = input()
t = input()

L = lcm(N, M)
l_to_s = {}
for i in range(N):
    l_to_s[1 + i * (L // N)] = i
l_to_t = {}
for i in range(M):
    l_to_t[1 + i * (L // M)] = i

ans = L
for k, v in l_to_s.items():
    if k in l_to_t:
        if s[v] != t[l_to_t[k]]:
            ans = -1
            break

print(ans)

Submission status: Accepted

Solution code:
# your code goes here
N,M = map(int,input().split())
 
S = input()
T = input()
 
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
 
if gcd(N,M) == 1:
	if S[0]==T[0]:
		print(N*M)
	else:
		print(-1)
else:
	tmp = gcd(N,M)
 
	ans = True
	for i in range(tmp):
		if S[N//tmp*i] != T[M//tmp*i]:
			ans = False
	if ans == True:
		print(N * M // tmp)
	else:
		print(-1)

Submission status: Accepted

Solution code:
# encoding: utf-8
N, M = map(int, input().split())
S = input()
T = input()

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

tmpans = N * M // gcd(N, M)
S_intv = tmpans // N
T_intv = tmpans // M

for sidx, si in enumerate(S):
    # skip
    idx = sidx * S_intv
    if idx % T_intv > 0: continue
    # else
    tidx = idx // T_intv
    if si != T[tidx]:
        ans = -1
        break
else:
    ans = tmpans

print(ans)

Submission status: Accepted

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

for i in range(x//y):
  if a[(x//m)*i] != b[(x//n)*i]:
    print(-1)
    exit()
print(x)

Submission status: Accepted

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
AGC028 A
"""

import fractions

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

g = fractions.gcd(n, m)
lcm = (n*m//g)

flag = True
for i in range(g):
    if s[i*lcm//m] != t[i*lcm//n]:
        flag = False
        break

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

Submission status: Accepted

Solution code:
import math

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

N, M = list(map(int, input().split()))
S = input()
T = input()
g = gcd(N, M)
lcm = N*M//g
if N%M==0 or M%N==0:
    exist = True
    if N>M:
        for i in range(M):
            if S[N//M*i]!=T[i]:
                exist = False
                break
    else:
        for i in range(N):
            if T[M//N*i]!=S[i]:
                exist = False
                break
    if exist:
        print(max(N, M))
    else:
        print(-1)
else:
    n_s = lcm//N
    n_t = lcm//M
    mul = n_s*n_t
    exist = True
    for i in range(0, lcm, mul):
        if S[i//n_s]!=T[i//n_t]:
            exist = False
            break
    if exist:
        print(lcm)
    else:
        print(-1)

Submission status: Accepted

Solution code:
def gcd(a, b):
	while b != 0:
		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)
n = L//N
m = L//M

sub_S = S[::m]
sub_T = T[::n]

if sub_S == sub_T:
    print(L)
else:
    print(-1)

Submission status: Accepted

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

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

n,m = [int(x) for x in input().split()]
s = input()
t = input()
l = lcm(n,m)
d = {}
for i in range(n):
  d[i * l / n] = s[i]
for i in range(m):
  if i in d and d[i * l / m] != t[i]:
    l = -1
    break

print(int(l))

Submission status: Accepted

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

Submission status: Accepted

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

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

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

else:
    p = f(N, M)
    k = N // p
    l = M // p

    for n in range(p):
        if S[n * k] != T[n * l]:
            print(-1)
            break
    else:
        print(N * M // p)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
def euc(n,m):
    if n%m == 0:
        return m
    else:
        return euc(m, n%m)
g = euc(N, M)
l = int(N*M/g)
S = input()
T = input()
steps = int(l/M)
stept = int(l/N)
stepnumber = int(N / steps)

for i in range(stepnumber):
    if S[i*steps] != T[i*stept]:
        print(-1)
        break
else:
    print(l)

Submission status: Accepted

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

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

sdic = {}
for k in range(0, len(s)):
    sdic[k*m] = s[k]
tdic = {}
for k in range(0, len(t)):
    tdic[k*n] = t[k]
ok = 1
for skey in sdic.keys():
    try:
        if tdic[skey] != sdic[skey]:
            ok = -1
    except:
        pass
    
if ok == 1:
    print(int(m * n / gcd(m,n)))
else:
    print('-1')

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def gcd(a,b):
    a, b = max(a,b), min(a,b)
    d = 1
    while a > b > 0:
        if a&1 == b&1 == 0:
            a >>= 1
            b >>= 1
            d <<= 1
        else:
            a, b = b, a%b
    d *= a
    return d

def solve():
    N, M = map(int,input().split())
    S = input()
    T = input()
    D = gcd(N,M)
    a = N//D
    b = M//D
    for i, j in zip(range(0,N,a), range(0,M,b)):
    	if S[i] != T[j]:
    		return '-1'
    L = N*M//D
    return str(L)

if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from fractions import gcd

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

g = int(gcd(N, M))
l = N * M // g

for i, j in zip(S[::N//g], T[::M//g]):
    if i != j:
        print(-1)
        break
else:
    print(l)

Submission status: Accepted

Solution code:
# cook your dish here
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)

jkl = (n-1)//(n//g)+1
nn = n//g
mm = m//g

c = 0
for i in range(jkl):

    if s[i*nn]==t[i*mm]:
        c += 1
    
if c == jkl:
    print(l)
else:
    print(-1)

Submission status: Accepted

Solution code:
n,m = (int(i) for i in input().split())
s = str(input())
t = str(input())
gcd = 0
r = n%m
n_gcd = n
m_gcd = m
while(r != 0):
    n_gcd = m_gcd
    m_gcd = r
    r = n_gcd%m_gcd
gcd = m_gcd
L_min = int(n*m/gcd)
flg = 1
for i in range(gcd):
    if s[int(n/gcd)*i]!= t[int(m/gcd)*i]:
        flg = 0
        break
if flg==1:
    print(L_min)
else:
    print(-1)

Submission status: Accepted

Solution code:
import fractions

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

s = list(input())
t = list(input())

l = len(s)
u = len(t)

a = fractions.gcd(l,u)
b = (l*u)//a

for i in range(a):
	if s[(l//a)*i]  != t[(u//a)*i]:
		print(-1)
		break
else:
	print(b)

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)
tmp = {}
for s, i in zip(S, range(0, lcm, lcm//N)):
    tmp[i] = s
is_ans = True
for t, i in zip(T, range(0, lcm, lcm//M)):
    if i in tmp:
        if tmp[i] == t:
            continue
        is_ans = False
        break
if is_ans:
    print(lcm)
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 = l // n
q = l // m
r = (p * q) // gcd(p, q)

ans = l

for i in range(l//r):
    if s[r//p*i] != t[r//q*i]:
        ans = -1
        break

print(ans)

Submission status: Accepted

Solution code:
import fractions

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

flag = False
gcd = fractions.gcd(n, m)
lcm = n * m // gcd
if s[0] == t[0]:
    if gcd == 1:
        flag = True
    else:
        if s[::lcm//len(t)] == t[::lcm//len(s)]:
            flag = True
if flag:
    print(lcm)
else:
    print(-1)

Submission status: Accepted

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

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


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

ok = True
nn = l // n
mm = l // m

i = 0
j = 0

while True:
    if i < j:
        i += nn
    elif j < i:
        j += mm
    else:
        if i // nn < n and j // mm < m:
            if s[i // nn] != t[j // mm]:
                ok = False
        else:
            break
        i += nn
    #print(i, j, nn, mm)

print(l if ok else -1)

Submission status: Accepted

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

Submission status: Accepted

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

N, M = map(int, input().split())
Ss = input()
Ts = input()

g = gcd(N, M)
ds, dt = N // g, M // g

if Ss[::ds] == Ts[::dt]:
    print(N * M // g)
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)
n = L//N
m = L//M
f = True
for i in range(N):
  if (i*n)%m == 0:
    if S[i] != T[(i*n)//m]:
      f = False
      break
print(L if f else -1)

Submission status: Accepted

Solution code:
import sys
import socket

if socket.gethostname() in ['N551J', 'F551C']:
    sys.stdin = open('a1.in')


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


def read_int():
    return int(input())


def read_str_list():
    return input().split()


def read_str():
    return input()


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


def solve():
    n, m = read_int_list()
    a = read_str()
    b = read_str()
    d = gcd(n, m)
    if a[::n // d] == b[::m // d]:
        lcm = n * m // d
        return lcm
    return -1


def main():
    res = solve()
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

def lcm(a, b):
    g = gcd(a, b)
    g_a = a // g
    g_b = b // g
    return g_a * g_b * g

L = lcm(n, m)
s1 = L // n
t1 = L // m
l = lcm(s1, t1)

flag = 0
for i in range(L//l):
    if s[i*t1] != t[i*s1]:
        flag = 1

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

Submission status: Accepted

Solution code:
# your code goes here
N,M = map(int,input().split())

S = input()
T = input()

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

if gcd(N,M) == 1:
	if S[0]==T[0]:
		print(N*M)
	else:
		print(-1)
else:
	tmp = gcd(N,M)

	ans = True
	for i in range(tmp):
		if S[N//tmp*i] != T[M//tmp*i]:
			ans = False
	if ans == True:
		print(N * M // tmp)
	else:
		print(-1)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

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

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

k = gcd(n,m)
k_n = int(n/k) #3
k_m = int(m/k) #2

s_a = s[0::k_n]
t_a = t[0::k_m]

if s_a == t_a:
    print(int(n*m/k))
else:
    print(-1)

Submission status: Accepted

Solution code:
import fractions

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

gcd_N_M = fractions.gcd(N, M)
lcm_N_M = N*M//gcd_N_M
if S[0::N//gcd_N_M] == T[0::M//gcd_N_M]:
    print(lcm_N_M)
else:
    print(-1)

Submission status: Accepted

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

s_in = lambda: stdin.readline()[:-1] # s = s_in()
d_in = lambda: int(stdin.readline()) # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split())) # List = ds_in()

N, M = ds_in()
S = s_in()
T = s_in()

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


# 最小公倍数
def lcm(a, b):
	return a * b // gcd (a, b)

lcm_NM = lcm(N, M)
for i in range(N * M // lcm_NM):
    if S[i*lcm_NM//M] != T[i*lcm_NM//N]:
        print(-1)
        exit()

print(lcm_NM)

Submission status: Accepted

Solution code:
def getN():
    return int(input())


def getNM():
    return map(int, input().split())


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

def gcd(n,m):
    if n > m:
        n,m = m,n
    while (m % n != 0):
        temp = n;
        n = m % n;
        m = temp;
    return n;

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

N,M = getNM()

s = input()
t = input()

lcm = lcm(N,M)
ks, kt = lcm//N, lcm//M
order = {}
flag = 1
i = 0
for alp in s:
    order[ks*i+1] = alp
    i += 1

j= 0
for alp in t:
    num = kt*j+1
    try:
        if order[num] != alp:
            flag = 0
    except:
        pass
    j += 1

if flag:
    print(lcm)
else:
    print("-1")

Submission status: Accepted

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

f=lambda x,y:x*y//gcd(x,y)
n,m=map(int,input().split())
s,t=input(),input()
lcm=f(n,m)
a,b=lcm//n,lcm//m
d={}

for i in range(n):
  d[i*a]=s[i]
for i in range(m):
  if i*b in d and d[i*b]!=t[i]:
    print(-1)
    break
  d[i*b]=t[i]
else:
  print(lcm)

Submission status: Accepted

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

N, M = map( int, input().split())
g = gcd(N,M)
S = input()
T = input()
c = M//g
t = N//g
ans = M*N//g
for i in range(N):
    if c*i%t == 0:
        if S[i] != T[c*i//t]:
            ans = -1
print(ans)

Submission status: Accepted

Solution code:
import math
import fractions

n, m = [int(i) for i in input().split()]
s = input()
t = input()

ans = n * m // fractions.gcd(n, m)

for scnt in range(n):
    if scnt * m % n == 0:
        tcnt = scnt * m // n
        if s[scnt] != t[tcnt]:
            ans = -1
            break

print(ans)

Submission status: Accepted

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


def main():
    n, m = map(int, raw_input().split())
    s = raw_input().strip()
    t = raw_input().strip()
    g = gcd(n, m)
    lcm = n * m / g
    a = lcm / m
    b = lcm / n
    if s[::a] == t[::b]:
        print lcm
    else:
        print -1


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#! usr/bin/env python
# -*- coding: utf-8 -*-


def gcd(a, b):
    if not b:
        return a
    return gcd(b, a % b)


def main():
    n, m = map(int, input().split())
    s, t = input(), input()
    l = n // gcd(n, m) * m

    dic = {}
    for i in range(n):
        dic[i*l//n+1] = s[i]

    for i in range(m):
        if i * l // m + 1 in dic and dic[i*l//m+1] != t[i]:
            print(-1)
            exit()

    print(l)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

from fractions import gcd
L = N*M//gcd(N,M)

ds = L//N

dt = L//M


print(L if S[::dt]==T[::ds] else -1)

Submission status: Accepted

Solution code:
def gcd(x,y):
    if x < y:
        (x,y) = (y,x)
    while y > 0:
        r = x % y
        x = y
        y = r
    return x


n,m = map(int, input().split())
s = str(input())
t = str(input())
lcm = (n*m) // gcd(n,m)

ind_s = lcm // m
ind_t = lcm // n

list_s = s[0::ind_s]
list_t = t[0::ind_t]

if list_s == list_t:
	print(lcm)
else:
	print(-1)

Submission status: Accepted

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


def gcd(x, y):
    return int(fractions.gcd(x, y))


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


tmp = input()
N, M = [int(a) for a in tmp.split()]
S = str(input())
T = str(input())
S_len = len(S)
T_len = len(T)

check_num = gcd(S_len, T_len)
S_skip = S_len // check_num
T_skip = T_len // check_num

ok = True
S_i = T_i = 0
for i in range(check_num):
    if S[S_i] != T[T_i]:
        ok = False
        break
    S_i += S_skip
    T_i += T_skip

if ok:
    print(lcm(S_len, T_len))
else:
    print(-1)

Submission status: Accepted

Solution code:
import math
import fractions
n,m = map(int,input().split())
lis = []
nn = n
mm = m
for i in range(2,math.ceil(math.sqrt(max(n,m)))+1):
  while nn % i == 0 and mm % i == 0:
    nn = nn // i
    mm = mm // i
num = (n * m)// fractions.gcd(n,m)
s = str(input())
t = str(input())
s = s[::nn]
t = t[::mm]
if s == t:
  print(num)
else:
  print("-1")

Submission status: Accepted

Solution code:
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)
    
def lcm(a, b):
	return a * b // gcd (a, b)
	
	
a = input().split()
a = [int(i) for i in a]

string1 = input()
string2 = input()

num = lcm(len(string1), len(string2))

counter = 0

one = num//len(string1)
two = num//len(string2)

ok = True
while counter*two < len(string1) and counter*one < len(string2):
	if string1[two*counter] == string2[one*counter]:
		pass
	else:
		ok = False
		break
	counter +=1
	
if ok == True:
	print(num)
else:
	print(-1)