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
n,m=map(int,input().split())
s=str(input())
t=str(input())
f=fractions.gcd(n,m)
f2=n*m//f
#print(f2)
for i in range(f2,n*m+1,f2):
    z2=(i//n)*(i//m)//fractions.gcd(i//n,i//m)
    for j in range(1,i+1,z2):
        #print(i,j)
        if s[-(-j//(i//n))-1]!=t[-(-j//(i//m))-1]:
            break
    else:
        print(i)
        break
else:
    print(-1)

Submission status: Accepted

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

print(ans)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.readline
readlines = sys.stdin.buffer.readlines

N, M = map(int, readline().split())
S = readline()
T = readline()
S = list(S.rstrip())
T = list(T.rstrip())
def gcd(a, b):
    while b:
        a, b = b, a%b
    return a

g = gcd(N, M)
l = N * M // g
x = l // N
y = l // M

if S[::y] != T[::x]:
    print(-1)
    exit()
print(l)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.readline
readlines = sys.stdin.buffer.readlines

N, M = map(int, readline().split())
S = readline()
T = readline()
S = list(S.rstrip())
T = list(T.rstrip())
def gcd(a, b):
    while b:
        a, b = b, a%b
    return a

g = gcd(N, M)
l = N * M // g
x = l // N
y = l // M

for i,s in enumerate(S[::y]):
    if s != T[x*i]:
        print(-1)
        exit()
print(l)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

N,M = map(int,input().split())
S = input()
T = input()
g = gcd(N,M)
N1 = N//g
M1 = M//g

bl = True
for i,s in enumerate(S[::N1]):
    if s != T[M1*i]:
        bl = False
        break

answer = N * M1 if bl else -1
print(answer)

Submission status: Accepted

Solution code:
import fractions

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

Submission status: Accepted

Solution code:
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N, M = list(map(int, sys.stdin.buffer.readline().split()))
S = sys.stdin.buffer.readline().decode().rstrip()
T = sys.stdin.buffer.readline().decode().rstrip()

g = gcd(N, M)
ok = True
for c, d in zip(S[::N//g], T[::M//g]):
    ok &=c == d
if ok:
    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()
p=gcd(n,m)
ans=n*m//p 
for i in range(n):
	if abs((i*(ans//n)/(ans//m))-int(i*(ans//n)/(ans//m)))<=10**(-7):
		if s[i]==t[(i*(ans//n)//(ans//m))]:
			continue
		else:
			print(-1)
			exit()
print(ans)

Submission status: Accepted

Solution code:
# AGC028
from fractions import gcd
#from math import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)

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

if N == l:
    tmp = N // M
    for i in range(tmp):
        if S[i * tmp] == T[i]:
            pass
        else:
            print(-1)
            exit()
if M == l:
    tmp = M // N
    for i in range(tmp):
        if T[i * tmp] == S[i]:
            pass
        else:
            print(-1)
            exit()

G = gcd(N, M)
if G != 1:
    for g in range(G):
        if S[g * N // G] == T[g * M // G]:
            pass
        else:
            print(-1)
            exit()
print(l)

Submission status: Accepted

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

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

l = lcm(n, m)
x, y = l // n, l // m

if all(s[i*y] == t[i*x] for i in range(gcd(n, m))):
    print (l)
else:
    print (-1)

Submission status: Accepted

Solution code:
import fractions
import bisect

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

A=(N//fractions.gcd(N,M))*M

NL=[0]*N
ML=[0]*M

for i in range(N):
    NL[i]=i*(A//N)


for i in range(M):
    ML[i]=i*(A//M)


ANDL = sorted(list(set(NL) & set(ML)))

for i in ANDL:
    St=bisect.bisect_left(NL,i)
    Tt=bisect.bisect_left(ML,i)
    if(S[St]!=T[Tt]):
        print("-1")
        exit()
print(A)

Submission status: Accepted

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

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

# 最小公倍数を求める
if N == M:
    l = -1
    if S == T:
        l = N
else:
    if N > M:
        w_n, w_m = N, M
        w_s, w_t = S, T
    else:
        w_n, w_m = M, N
        w_s, w_t = T, S

    if w_n % w_m == 0:
        k = w_n // w_m
        is_ok = True
        l = len(w_s)
        for i, char in enumerate(w_t):
            if S[(i - 1) ** k] != char:
                is_ok = False
                break
        if not is_ok:
            l = -1
    else:
        # 最小公倍数が候補
        l = w_m * w_n // fractions.gcd(w_m, w_n)
        is_ok = True
        s_idx_list = []
        t_idx_list = []

        # w_mの方が小さいのでw_mを基準にする
        for i in range(w_n):
            s_idx_list.append(i * (l // w_n))
            t_idx_list.append(i * (l // w_m))
        common_idx_list = list(set(s_idx_list) & set(t_idx_list))

        for j in common_idx_list:
            s_idx = w_n * j // l
            t_idx = w_m * j // l
            if t_idx > w_m - 1:
                break
            if w_s[s_idx] != w_t[t_idx]:
                is_ok = False
                break
        if not is_ok:
            l = -1

ans = l

print(ans)

Submission status: Accepted

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

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

k=N*M//gcd(N,M)
X=[0]*N
for i,s in enumerate(S):
  X[i]=s
  
for i,t in enumerate(T):
  if (i*k//M)%(k//N)!=0:
    pass
  elif (i*k//M)%(k//N)==0 and X[(i*k//M)//(k//N)]==t:
    pass
  else:
    print(-1)
    exit()
    
print(k)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=input()
t=input()
from fractions import gcd
def lcm(x,y):
  return (x*y)//gcd(x,y)
g=gcd(n,m)
a=n//g;b=m//g
x=lcm(n,m)
for i in range(g):
  if s[a*i]!=t[b*i]:
    x=-1
    break
print(x)

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 = map(int, input().split())
s = input()
t = input()

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

lcm_ = lcm(N, M)

x = 0
while x * n < N and x * m < M:
    if s[x * n] != t[x * m]:
        print(-1)
        exit()
    x += 1
print(lcm_)

"""
0-indexedで考える。
s : x[0], x[k*L/N], x[k*L/N*2], ...
t : x[0], x[k*L/M], x[k*L/M*2], ...
同じindexを指しているとき、同じ文字である必要がある。

len(x)はlcm(N,M)の倍数。

N = gn
M = gm
L = gnm = NM/g

s : x[0], x[k*M/g], x[k*M/g*2], ... x[k*M/g*a], ...
t : x[0], x[k*N/g], x[k*N/g*2], ... x[k*N/g*b], ...

k*M/g*a==k*N/g*b

kにかかわらず
if ma==nb:
    # m,nは互いに素なので、a=xn, b=xm
    if s[a] != t[b]:
        return False
"""

Submission status: Accepted

Solution code:
from fractions import gcd


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

    g = gcd(n, m)

    def f(x):
        ret = ""
        for i in range(0, len(x), len(x) // g):
            ret += x[i]

        return ret

    if f(s) == f(t):
        ans = n * m // g
    else:
        ans = -1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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


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


st = gcd(s, t)
good = s * t // st

if S[::s // st] == T[::t // st]:
    print(good)
else:
    print(-1)

Submission status: Accepted

Solution code:
from fractions import gcd

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

st = gcd(s, t)
good = s * t // st

if S[::s // st] == T[::t // st]:
    print(good)
else:
    print(-1)

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)
        break
else:
    print((n*m)//g)

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 = map(int,input().split())
s=list(input())
t=list(input())
l=lcm(n,m)
g=gcd(n,m)
for i in range(g):
    if s[i*(n//g)]!=t[i*(m//g)]:
        l=-1
        break
print(l)

Submission status: Accepted

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

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

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

num=gcd(n,m)

if num==1:
    ans=n*m

else:
    ans=n*m//num
    check1=n//num
    check2=m//num
    for i in range(1,num):
        if s[i*check1]==t[i*check2]:
            continue
        else:
            print(-1)
            exit()
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

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

for i in range(k):
    if S[i * n] != T[i * m]:
        print(-1)
        exit()

print(lcm(N, M))

Submission status: Accepted

Solution code:
m, n = [ int(v) for v in input().split() ]
s = input()
t = input()


def gcd(a,b):
    if a < b:
        a, b = b, a
    while b >= 1:
        a, b = b, a % b
    return a
def lcm(a,b):
	return a * b // gcd(a,b)

g = gcd(m,n)

ds = [ v  for i, v in enumerate(s) if i % (m/g) == 0 ]
dt = [ v  for i, v in enumerate(t) if i % (n/g) == 0 ]
print( lcm(m,n) if ds == dt else -1 )

Submission status: Accepted

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

def gcd(x, y):
    while x != 0 and y != 0:
        x, y = min(x,y), max(x,y)
        y %= x
    return x

def aa():
    a = gcd(n, m)
    ss = n // a
    tt = m // a
    si = 0
    ti = 0
    for i in range(a):
        if s[si] != t[ti]:
            return -1
        si += ss
        ti += tt
    return n * m // a
print(aa())

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)


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


def main():
    n, m = map(int, input().split())
    s = input()
    t = input()
    g = gcd(n, m)
    n1 = n // g
    m1 = m // g

    b = True
    for i, v in enumerate(s[::n1]):
        if v != t[m1*i]:
            b = False
            break
    print(n * m1 if b else -1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def gcd(a, b):
    """a, bの最大公約数(greatest common divisor:GCD)を求める"""
    if b == 0:
        return a
    return gcd(b, a%b)


def lcm(a, b):
    """a, bの最小公倍数(least common multiple:LCM)を求める"""
    return (a * b) // gcd(a, b)


n, m = map(int, input().split())
s = input()
t = input()
gcd_nm = gcd(n, m)
s_num = n // gcd_nm
t_num = m // gcd_nm

for i in range(gcd_nm):
    if s[i*s_num] == t[i*t_num]:
        continue
    else:
        print(-1)
        break
else:
    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)
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:
import collections
import fractions
N, M = map(int, input().split())
S = input()
T = input()
lcm = (N*M) // fractions.gcd(N, M)
if S[0] != T[0]:
    print(-1)
elif N == M and S != T:
    print(-1)
else:
    tmp = lcm // N
    tmp2 = lcm // M
    tmp_s = collections.defaultdict(str)
    for i in range(N):
        tmp_s[tmp*i] = S[i]

    for i in range(M):
        if tmp2*i in tmp_s:
            if T[i] != tmp_s[tmp2*i]:
                print(-1)
                exit(0)
    print(lcm)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))


n,m = inpl()
s = list(input())
t = list(input())
if n < m:
    n,m = m,n
    s,t = t,s
ggg = n*m//fractions.gcd(n,m)
tn = ggg//n
tm = ggg//m
i = 0
while i*tm < n and i*tn < m:
    if s[i*tm] != t[i*tn]:
        print(-1)
        break
    i += 1
else:
    print(ggg)

Submission status: Accepted

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

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

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

L = lcm(N, M)
n = L // N
m = L // M
C = n * m

# print(N, M, L, n, m, S, T)

ans = True
for i in range(0, L, C):
    s = S[i // n]
    t = T[i // m]
    if s != t:
        ans = False
        break

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):
  while b:
    a,b=b,a%b
  return a
g=gcd(N,M)
L=N*M//g
if all(S[i*N//g]==T[i*M//g]for i in range(g)):
  print(L)
else:
  print(-1)

Submission status: Accepted

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


def euclid(x, y):
    x, y = max(x, y), min(x, y)
    if y == 0:
        return x
    return euclid(y, x % y)


lcm = n * m // euclid(n, m)
nn = lcm // n
mm = lcm // m
ss = s[0::mm]
tt = t[0::nn]

if ss == tt:
    print(lcm)
else:
    print(-1)

Submission status: Accepted

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

Submission status: Accepted

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

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

if S[0]==T[0]:
  g=gcd(N,M)
  if g==1:
    print(N*M)
  else:
    for i in range(0,g-1):
      n=N//g
      m=M//g
      if S[n*i]!=T[m*i]:
        print(-1)
        exit()
    print(N*M//g)
else:
  print(-1)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from fractions import gcd
    n,m=map(int,input().split())
    s,t=[input() for _ in range(2)]
    gcd=gcd(n,m)
    lcm=n*m//gcd
    n//=gcd
    m//=gcd
    print(lcm if all(s[n*i]==t[m*i] for i in range(gcd)) else -1)
resolve()

Submission status: Accepted

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

# len(S) >= len(T) にする
if N < M:
    S, T = T, S
    N, M = M, N

for j, t in enumerate(T):
    if j * N % M == 0:
        k = j * N // M
        s = S[k]
        if t != s:
            print('-1')
            exit()

def gcd(n, m):
    if m == 0:
        return n
    return gcd(m, n % m)

GCD = gcd(N, M)
LCM = N * M // GCD

print(LCM)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
S=input()
T=input()
from fractions import gcd
g=gcd(N,M)
r=1
j,k=0,0
for i in range(g):
    if S[j]!=T[k]:
        r=0
    j+=N//g
    k+=M//g
print(M*N//g if r else -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()

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

IsOk = True
for i in range(gcd(N, M)):
  if S[n * i] != T[m * i]:
    IsOk = False

if IsOk:
  print(lcm(N, M))
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)
L = (N * M) // G
div_N = N // G
div_M = M // G

i = 0
j = 0

while i < N and j < M:
  if S[i] != T[j]:
    print(-1)
    exit()
  else:
    i += div_N
    j += div_M
print(L)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
sys.setrecursionlimit(200000)
input = sys.stdin.readline

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

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

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

# m = [None] * l
m = {}

for i in range(N):
    m[i * (l // N)] = S[i]

for i in range(M):
    index = i * (l // M)
    if m.get(index) == None:
        m[index] = T[i]
    elif m[index] == T[i]:
        pass
    else:
        print(-1)
        exit()

print(l)

Submission status: Accepted

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

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

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

g = gcd(N, M)
i, j = 0, 0
ok = True
while i < N and j < M:
  if S[i] != T[j]:
  	ok = False
  i += N // g
  j += M // g
if ok:
  print(lcm(N,M))
else:
  print(-1)

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

gcd=gcd(M,N)

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

print((M*N)//gcd)

Submission status: Accepted

Solution code:
from fractions import gcd

def exist_good_str(N,M,S,T,L):
  X = {}
  for idx, s in enumerate(S):
    if idx != 0: idx = L//N*idx
    if idx in X and X[idx] != s: return False
    else: X[idx] = s
    
  for idx, t in enumerate(T):
    if idx != 0: idx = L//M*idx 
    if idx in X and X[idx] != t: return False
    else: X[idx] = t
  return True
      
N,M = map(int,input().split())
S,T = input(), input()

L = int((N * M / gcd(N, M)))
if exist_good_str(N,M,S,T,L) is True: print(L)
else: print(-1)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline

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

def main():
    N,M = map(int,input().split())
    S = input().strip()
    T = input().strip()
    L = lcm(N,M)
    for i in range(fractions.gcd(N,M)):
        if S[i*L//M] != T[i*L//N]:
            print("-1")
            return
    print(L)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from fractions import gcd
N,M=map(int,input().split())
S=input()
T=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:
import sys
input=sys.stdin.readline
import bisect

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

def main():
    N,M = map(int,input().split())
    S = input().strip()
    T = input().strip()
    m = lcm(N,M)
    for i in range(M):
        si = i*m//M
        ti = i*m//N
        if si < N and ti < M and S[si] != T[ti]:
            print("-1")
            return
    print(m)

if __name__ == '__main__':
    main()

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)
a = L//N
b = L//M
c = a*b//gcd(a,b)
i = 0
while i<L:
  if S[i//(L//N)] != T[i//(L//M)]:
    print(-1)
    exit()
  i += c
print(L)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

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

    n,m = LI()
    s = S()
    t = S()
    g = gcd(n,m)
    l = n*m//g
    n_ = n//g
    m_ = m//g
    for i in range(g):
        if s[n_*i] != t[m_*i]:
            print(-1)
            return
    print(l)
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    A()

Submission status: Accepted

Solution code:
def gcd(a,b):
  if a<b:
    a,b=b,a
  if a%b==0:
    return b
  return gcd(b,a%b)
  
N, M = map(int, input().split())
S = input()
T = input()
p = gcd(N, M)
n = N // p
m = M // p
for i in range(p):
  if S[i*n] != T[i*m]:
    print(-1)
    exit()
print((N*M)//p)

Submission status: Accepted

Solution code:
def main():

    N, M = map(int, input().split())
    S = input()
    T = input()
    p = gcd(N, M)
    n = N // p
    m = M // p
    for i in range(p):
        if S[i*n] != T[i*m]:
            return "-1"
    return p*n*m


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

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

Submission status: Accepted

Solution code:
import sys
import  math
import bisect
from statistics import *
from collections import *
from operator import itemgetter

from fractions import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n, m = na()
s = input()
t = input()
l = lcm(n, m)
flag = True
ln = l // n
lm = l // m
d = {}
ans = l
for i in range(n):
    d[1 + i * ln] = s[i]
for i in range(m):
    if 1 + i * lm in d.keys():
        if d[1 + i * lm] != t[i]:
            ans = -1
            break
print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd


N, M = map(int, input().split())
S, T = [input() for _ in range(2)]
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 collections import defaultdict
N, M = map(int,input().split())
S = input()
T = input()

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

    if a % b == 0:
        return b

    return gcd(b, a % b)

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

len_l = lcm(N, M)
dict = defaultdict(str)

for i, s in enumerate(S):
    dict[i * len_l//N] = s

for j, t in enumerate(T):
    if dict[j * len_l//M] != "" and dict[j * len_l//M] != t:
        print(-1)
        exit()

print(len_l)

Submission status: Accepted

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

def gcd(x,y):
    if x==y:
        return x
    elif x>y:
        r=-1
        while r!=0:
            r=x%y
            x=y
            y=r
        return x
    else:
        r=-1
        while r!=0:
            r=y%x
            y=x
            x=r
        return y

N=n//gcd(n,m)
M=m//gcd(n,m)
f=1
for i in range(gcd(n,m)):
    if s[i*N]!=t[i*M]:
        f=0
if f:
    print(n*m//gcd(n,m))
else:
    print(-1)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    n, m = list(map(int, input().rstrip('\n').split()))
    s = input().rstrip('\n')
    t = input().rstrip('\n')
    import fractions
    lcm = n * m // fractions.gcd(n, m)
    for i in range(0, n * m, lcm):
        if s[i // m] != t[i // n]:
            print(-1)
            exit()
    print(lcm)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, fractions, itertools, collections, copy, heapq


def solve(N: int, M: int, S: str, T: str):
    n = fractions.gcd(N, M)
    x = N * M // n

    flag = True
    for i in range(n):
        if S[i * x // M] == T[i * x // N]:
            pass
        else:
            flag = False
            break

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

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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:
from fractions import gcd

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

n = gcd(N, M)
#最小公倍数xを求める
x = N * M // n


flag = True
for i in range(n): #重なるのはgcdの個数分だけ
    # print (i)
    # print (i * x // M, i * x // N)
    if S[i * x // M] == T[i * x // N]:
        pass
    else:
        flag = False
        break

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

Submission status: Accepted

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

def main():
    N, M = map(int, input().split())
    s = input().strip()
    t = input().strip()
    if M > N:
        tmp = s
        s = t
        t = tmp
        tmp = N
        N = M
        M = tmp
    # N >= Mと仮定して良い
    gcd_ = gcd(N, M)
    len_ = N * (M//gcd_)
    tmp1 = len_ // N
    tmp2 = len_ // M
    # print(tmp1, tmp2)
    ok = True
    for i in range(0, len_, tmp1 * (tmp2//gcd(tmp1, tmp2))):
        # print(i, s[i//tmp1], t[i//tmp2])
        if s[i//tmp1] != t[i//tmp2]:
            ok = False
            break
    if ok:
        print(len_)
    else:
        print(-1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from fractions import gcd


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

Submission status: Accepted

Solution code:
import fractions

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

Submission status: Accepted

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

gcd = fractions.gcd(N,M)
ans = True
for i in range(gcd):
    if S[(N//gcd)*i] != T[(M//gcd)*i]:
        ans = False

if ans:
    print(N*M//gcd)
else:
    print(-1)

Submission status: Accepted

Solution code:
from fractions import gcd


def lcm(a, b):
    """
    aとbの最小公倍数を計算します。
    """
    return a * b // gcd(a, b)


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

ans = lcm(N, M)

c = dict()
for i in range(N):
    c[i * ans // N] = S[i]
for i in range(M):
    val = c.get(i * ans // M)
    if val is not None and val != T[i]:
        print(-1)
        exit(0)
print(ans)

Submission status: Accepted

Solution code:
def factorize2(n):
    """
    nの値を素因数分解し、素因数とその指数をtupleにまとめたリストを返す
    e.g.
    [(2, 2), (5, 1)]
    """
    b = 2
    fct = []
    while b * b <= n:
        cnt = 0
        while n % b == 0:
            cnt += 1
            n //= b
        if cnt > 0:
            fct.append((b, cnt))
        b += 1
    if n > 1:
        fct.append((n, 1))
    return fct


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

d = dict()
for num, pow in factorize2(N):
    d[num] = pow
for num, pow in factorize2(M):
    if d.get(num) is None:
        d[num] = pow
    elif d[num] < pow:
        d[num] = pow
ans = 1
for num, pow in d.items():
    ans *= num ** pow

c = dict()
for i in range(N):
    c[i * ans // N] = S[i]
for i in range(M):
    val = c.get(i * ans // M)
    if val is not None and val != T[i]:
        print(-1)
        exit(0)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from fractions import*
n,m = map(int,input().split())
g = gcd(n,m)
print(n*m//g if input()[::n//g] == input()[::m//g] else -1)

Submission status: Accepted

Solution code:
# 2019/08/11

from fractions import gcd

n,m=map(int,input().split())
s=input()
t=input()
lcd=(n*m)//gcd(n,m)
x={}
aa=(lcd//n)
bb=(lcd//m)
for i in range(n):
    a=i*aa
    x[a]=s[i]

for i in range(m):
    b=i*bb
    if b in x and x[b]!=t[i]:
        print(-1)
        exit()
    
print(lcd)