Problem:


Score : 300 points

Problem Statement

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

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

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

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

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

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

Constraints

1 \leq N,M \leq 10^5

S and T consist of lowercase English letters.

|S|=N

|T|=M

Input

Input is given from Standard Input in the following format:

N M
S
T

Output

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

Sample Input 1

3 2
acp
ae

Sample Output 1

6

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

Sample Input 2

6 3
abcdef
abc

Sample Output 2

-1

Sample Input 3

15 9
dnsusrayukuaiia
dujrunuma

Sample Output 3

45



Sample input:
3 2
acp
ae


Sample output:
6

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#AGC28 A

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

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,sys.stdin.readline().split())
s = input()
t = input()
l = lcm(n,m)
a,b = n//gcd(n,m),m//gcd(n,m)
for i in range(min(n//a,m//b)):
    if s[a*i] != t[b*i]:
        print(-1)
        quit()
print(l)

Submission status: Accepted

Solution code:
from fractions import gcd
N,M=map(int,input().split())
S=input()
T=input()
s=(M//gcd(N,M))
t=(N//gcd(N,M))
SS=[i*s for i in range(N)]
TT=[j*t for j in range(M)]
p,q=0,0
ans=N*s
while True:
    if SS[p]==TT[q]:
        if S[p]!=T[q]:ans=-1
        p+=1
        q+=1
    elif SS[p]>TT[q]:
        q+=1
    else:
        p+=1
    if p==N or q==M:
        break
print(ans)

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
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

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

a = lcm(N, M)
b = lcm(a//N, a//M)

l = [0]
tmp = 0
while tmp < a:
    tmp += b
    if tmp < a:
        l.append(tmp)

#print(a, b, l)

check = 0

for i in range(len(l)):
#    print(S[l[i]//(a//N)], T[l[i]//(a//M)])
    if S[l[i]//(a//N)] == T[l[i]//(a//M)]:
        pass
    else:
        check = 1 

if check == 0:
    ans = a
else:
    ans = -1

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *

N, M = map(int, input().split())
S, T = input(), input()
gcd = lambda a, b: a if b == 0 else gcd(b, a%b)
g = gcd(N, M)
n, m = N//g, M//g
for i in range(min(N//n, M//m)):
    if S[n*i] != T[m*i]:
        print(-1)
        exit()
print(N*M//g)

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
ans = lcm


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

Submission status: Accepted

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


def main():
    N, M = map(int, input().split())
    s = input()
    t = input()
    d = gcd(N, M)
    for i in range(d):
        if s[i*N//d] != t[i*M//d]:
            print(-1)
            return
    print(N*M//d)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def g_c_d(x, y):
    if x == 0:
        return y
    elif y == 0:
        return x
    else:
        return g_c_d(y, x % y)


def l_c_m(x, y):
    return x * y // g_c_d(x, y)


a, b = map(int, input().split())
c = input()
d = input()
lcm = l_c_m(a, b)
gcd = g_c_d(a, b)
for i in range(0, gcd):
    if c[i * a // gcd] != d[i * b // gcd]:
        print(-1)
        exit()
print(lcm)

Submission status: Accepted

Solution code:
# AGC028A - Two Abbreviations
def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a


def main():
    n, m = tuple(map(int, input().rstrip().split()))
    S, T = tuple(input().rstrip() for _ in range(2))
    g = gcd(n, m)
    flg = S[:: n // g] == T[:: m // g]
    print(n // g * m if flg else -1)


if __name__ == "__main__":
    main()

Submission status: Accepted

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


def main():
    n, m = tuple(map(int, input().rstrip().split()))
    S, T = tuple(input().rstrip() for _ in range(2))
    g = gcd(n, m)
    flg = S[:: n // g] == T[:: m // g]
    print(n // g * m if flg else -1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# AGC028
from fractions import gcd


def main():
    n, m = tuple(map(int, input().rstrip().split()))
    S, T = tuple(input().rstrip() for _ in range(2))
    l = n // gcd(n, m) * m
    x = {}
    for i in range(n):  # place S in x
        j = (l // n) * i
        x[j] = S[i]
    for i in range(m):  # check T adapts to x or not
        j = (l // m) * i
        if j in x and x[j] != T[i]:
            print(-1)
            break
    else:
        print(l)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import exit
import math
from fractions import gcd

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

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

    else:
        print(-1)
    exit()
    
if N<M:
    N,M=M,N
    S,T=T,S
    

# N>M S>T
if(N%M==0):
    S2=""
    for i in range(N):
        if i%(N//M)==0 :
            S2+=S[i]
            
    if S2==T:
        print(N)
    else:
        print(-1)
    exit()

else:
    g=gcd(N,M)
    S2=""
    for i in range(N):
        if i%(N//g)==0 :
            S2+=S[i]
    T2=""
    for i in range(M):
        if i%(M//g)==0 :
            T2+=T[i]
    if S2==T2:
        print(lcm(N,M))
    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)

N_step=L//N
M_step=L//M
X_step=N_step*M_step//fractions.gcd(N_step,M_step)

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

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

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

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

print(lcm)

Submission status: Accepted

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

def gcd(x, y):
    while y > 0:
        x, y = y, x%y
    return x
 
def lcm(x, y):
    return int(x/gcd(x, y)*y)

lenx = lcm(N,M)

s_list = list(S)
t_list = list(T)

baisuu_s = int(lenx/N)
baisuu_t = int(lenx/M)
def check():
    for i in range(0,lenx,baisuu_s):
        if i % baisuu_s==0 and i%baisuu_t == 0:
            if s_list[int(i/baisuu_s)] == t_list[int(i/baisuu_t)]:
                pass
            else:
                return False
    return True

if check():
    print(lenx)
else:
    print(-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from collections import defaultdict, deque
import math
from math import factorial
import fractions
import re

BIGNUM = 10 ** 9 + 7

def main():
    L, N = map(int, input().split())
    S = list(input())
    T = list(input())
    
    lcm = len(S) * len(T) // fractions.gcd(len(S), len(T))
    gcd = fractions.gcd(len(S), len(T))
    S_unit = len(S) // gcd
    T_unit = len(T) // gcd

    for i in range(gcd):
        if S[i*S_unit] != T[i*T_unit]:
            print(-1)
            return
    print(lcm)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,M=list(map(int,input().strip().split(' ')))
A=input()
B=input()
def gcd(a,b):
    if a>b:
        a,b=b,a
    if b%a==0:
        return a
    return gcd(b%a,a)
g=gcd(M,N)
m=M//g
n=N//g
flag=1
for r in range(g):
    if A[n*r]!=B[m*r]:
        flag=0

if flag==1:
    print(g*m*n)
else:
    print(-1)

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)
    smatch = []
    tmatch = []
    flag = True
    for i in range(g):
        smatch.append(s[i*(n//g)])
        tmatch.append(t[i*(m//g)])
    for k,l in zip(smatch,tmatch):
        if k != l:
            flag = False

    if flag:
        print(n*m//g)
    else:
        print(-1)


main()

Submission status: Accepted

Solution code:
from fractions import gcd

N, M = map(int, input().split()) # 横に2個
S = input()
T = input()
Gcd = gcd(N, M)
Np = N // Gcd
Mp = M // Gcd

ans = Gcd * Mp * Np
for g in range(Gcd):
    if S[g*Np] != T[g*Mp]:
        ans = -1
        break

print(ans)

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,t=input(),input()
a=gcd(n,m)
m//=a
for i in range(a):
  if s[(n//a)*i]!=t[m*i]:print(-1);exit()
print(m*n)

Submission status: Accepted

Solution code:
from sys import stdin
import fractions
N,M = [int(x) for x in stdin.readline().rstrip().split()]
S = (stdin.readline().rstrip())
T = (stdin.readline().rstrip())
g = fractions.gcd(N,M)
def lcm(a, b):
    return a * b / fractions.gcd(a, b)
flag = True
for i in range(g):
    if S[(i*N)//g] != T[(i*M)//g]:
        flag = False
        break
if flag:
    print(int(lcm(N,M)))
else:
    print(-1)

Submission status: Accepted

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

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

gc = gcd(n,m)
lcm = n * m // gc
s = input()
t = input()

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

Submission status: Accepted

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

if gcd == 1:
  if s[0] == t[0]:
    print(lcm)
  else:
    print(-1)
else:
  if s[::n//gcd] == t[::m//gcd]:
    print(lcm)
  else:
    print(-1)

Submission status: Accepted

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


def LCM(a, b):
    return a * b // GCD(a, b)

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

l = LCM(n, m) # = 45
k = l//GCD(n, m) # = 15
flag = True
for i in range(l//k):
    if s[k*i//(l//n)] != t[k*i//(l//m)]:
        flag = False

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

Submission status: Accepted

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

def solve(n, m, s, t):
    if n < m:
        s, t = t, s
        n, m = m, n
    if n % m == 0:
        l = n
    else:
        l = n * m // gcd(n, m)
    D = {}
    for i in range(n):
        D[i*l//n] = s[i]
    for i in range(m):
        k = i*l//m
        if (k in D) and (D[k] != t[i]):
            return -1
    return l

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
A - Two Abbreviations
https://atcoder.jp/contests/agc028/tasks/agc028_a

"""
import sys

from fractions import gcd

def solve(N, M, S, T):
    lcm = N * M // gcd(N, M)
    res = dict()
    for i, s in zip(range(0, lcm+1, lcm//N), S):
        res[i] = s
    for j, t in zip(range(0, lcm+1, lcm//M), T):
        if j in res and res[j] != t:
            return -1
    return lcm


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


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
S = input()
T = input()
#良い文字列は存在するならば長さはN,Mの最小公倍数になる
#異なる文字が同じ場所に来たらダメ
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)
n = N//gcd(N,M)
m = M//gcd(N,M)
for k in range(gcd(N,M)):
    if S[k*n] != T[k*m]:
        print(-1)
        exit()
print(L)

Submission status: Accepted

Solution code:
from fractions import gcd
str_1_len, str_2_len = map(int, input().split())
string_1 = input()
string_2 = input()

gr_com_div = gcd(str_1_len, str_2_len)
low_com_multpl = int(str_1_len * str_2_len / gr_com_div)
flg = True

for i in range(gr_com_div):
    if string_1[i*str_1_len//gr_com_div] == string_2[i*str_2_len//gr_com_div]:
        continue
    else:
        flg = False
if flg:
    print(low_com_multpl)
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)
h = N * M // g

si = 0
ti = 0

for _ in range(g):
    if S[si] != T[ti]:
        print(-1)
        break
    si += N // g
    ti += M // g
else:
    print(h)

Submission status: Accepted

Solution code:
from fractions import gcd
from math import sqrt
from heapq import *
from math import factorial
from collections import defaultdict

N,M=map(int,input().split())
S=input()
T=input()
g=gcd(N,M)
m=(N//g)*(M//g)*g
a=0
b=0
A=m//N
B=m//M
t=True
while(a<N):
    if S[a]==T[b]:
        a+=B
        b+=A
    else:
        print(-1)
        quit()
print(m)

Submission status: Accepted

Solution code:
def gcd(x, d):
    if x < d:
        x, d = d, x
    if x % d == 0:
        return d
    return gcd(d, x % d)


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

lcm = (n * m) // gcd(n, m)
sSub = [s[i] for i in range(0, n, lcm // m)]
tSub = [t[j] for j in range(0, m, lcm // n)]

if sSub == tSub:
    print(lcm)
else:
    print(-1)

# print(*data, sep='\n')

Submission status: Accepted

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

S = input()
T = input()


arr1 = [0]*(max(N, M) + 1)
arr2 = [0]*(max(N, M) + 1)


def factoring(arr, tmp):
    i = 1
    while i < tmp:
        i += 1
        if tmp % i == 0:
            tmp = tmp // i
            arr[i] += 1
            i = 1
    
factoring(arr1, tmp=N)
factoring(arr2, tmp=M)

U = 1
for i in range(2, max(N, M)+1):
    tmp = max(arr1[i], arr2[i])
    if tmp != 0:
        U *= i**tmp
V = 1
for i in range(2, max(N, M)+1):
    tmp = min(arr1[i], arr2[i])
    if tmp != 0:
        V *= i**tmp


def good_str(N, M, S, T):
    n = 0
    m = 0
    while n < N and m < M:
        if M*n == N*m:
            if S[n] != T[m]:
                return False
        if M*n > N*m:
            m += 1
        else:
            n += 1
    return True


if good_str(N, M, S, T):
    print(U)
else:
    print(-1)

Submission status: Accepted

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


def gcd(x,y):
    z = x % y
    if z==0:
        return y
    else:
        return gcd(y,z)
    
def lcm(x,y):
    return x*y//gcd(x,y)

L = lcm(N,M)
m1 = L // N
m2 = L // M
mlcm = lcm(m1,m2)
idx = 0
flag = True
while True:
    sid = mlcm*idx//m1
    tid = mlcm*idx//m2
    if sid >= N or tid >= M: break    
    if S[sid] != T[tid]:
        flag = False
        break
    idx += 1

if flag:
    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
g = gcd(n,m)
x = n*m//gcd(n,m)
d = dict()
a,b = n//g,m//g
for i in range(n):
  d[i*b] = s[i]
for j in range(m):
  if j*a in d and d[j*a] != t[j]:
    print(-1)
    break
else:
  print(x)

Submission status: Accepted

Solution code:
from fractions import gcd

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

s = input()
t = input()

div = gcd(n, m)
div_n = n // div
div_m = m // div

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

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from fractions import gcd
n,m = map(int,input().split())
g = gcd(n,m)
if input()[::n//g] == input()[::m//g]:
  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()
g = gcd(n,m)
if s[::n//g] == t[::m//g]:
  print(n*m//g)
else:
  print(-1)

Submission status: Accepted

Solution code:
def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    c = a % b
    return gcd(b, c)
  
N,M = [ int(it) for it in input().split() ]
S = input()
T = input()
P = gcd(N,M)
NP = N//P
MP = M//P
NPMP = NP*MP
flag = True
for i in range( P ):
  if ( S[NP*i] != T[MP*i] ):
    flag = False

print (NPMP*P) if flag else print (-1)

Submission status: Accepted

Solution code:
gcd=lambda a,b: a if b==0 else gcd(b,a%b)
n,m=map(int,input().split())
s=input()
t=input()
d=gcd(n,m)
a = n*m//d if s[::n//d]==t[::m//d] else -1
print(a)

Submission status: Accepted

Solution code:
gcd = lambda a,b: a if b==0 else gcd(b,a%b)
n,m = map(int,input().split())
s = input()
t = input()
d = gcd(n,m)
if s[::n//d]==t[::m//d]:
    print(n*m//d)
else:
    print(-1)

Submission status: Accepted

Solution code:
gcd = lambda a,b: a if b==0 else gcd(b,a%b)
n,m = map(int,input().split())
s = input()
t = input()
a = m//gcd(n,m)
b = n//gcd(n,m)
if s[::b]==t[::a]:
    print(n*m//gcd(n,m))
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)
n, m = N//g, M//g

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

Submission status: Accepted

Solution code:
def gcd(a,b):
	x,y = min(a,b), max(a,b)
	while x*y>0:
		x,y = y%x,x
	return y

N,M=map(int,input().split())
S=input()
T=input()
g=gcd(N,M)
p,q=M//g,N//g
print((N//g)*M) if S[0::q]==T[0::p] else print('-1')

Submission status: Accepted

Solution code:
def gcd(a,b):
	x,y = min(a,b), max(a,b)
	while x*y>0:
		x,y = min(x,y), max(x,y)
		x,y = y-x,x
	return y

N,M=map(int,input().split())
S=input()
T=input()
g=gcd(N,M)
p,q=M//g,N//g
print((N//g)*M) if S[0::q]==T[0::p] else print('-1')

Submission status: Accepted

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

import fractions
import sys
from collections import defaultdict

N, M = map(int, input().rstrip().split(' '))
S = [x for x in input()]
T = [x for x in input()]

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

L = lcm(N, M)

dp = defaultdict(lambda: -1)

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

for i, t in enumerate(T):
    if dp[i*L//M] != -1:
        if dp[i*L//M] != t:
            print(-1)
            sys.exit()
print(L)

Submission status: Accepted

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

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

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)

tmp = T
ss = L//N
tt = L//M
for i in range(N):
    if (i * ss) % tt == 0:
        if S[i] != T[(i*ss)//tt]:
            print('-1')
            quit()

print(L)

Submission status: Accepted

Solution code:
import fractions
n,m=map(int,input().split())
s=input()
t=input()
l=n*m//fractions.gcd(n,m)
p=l//n*l//m//fractions.gcd(l//n,l//m)
ss,tt="",""
for i in range(l//p):
  ss+=s[i*p*n//l]
  tt+=t[i*p*m//l]
print(l if ss==tt else -1)

Submission status: Accepted

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

GCD = gcd(N, M)
LCM = int(N * M / GCD)
flg = True

for i in range(GCD):
    if S[i*N//GCD] == T[i*M//GCD]:
        continue
    else:
        flg = False
if flg:
    print(LCM)
else:
    print(-1)

Submission status: Accepted

Solution code:
#E問題
N,M=map(int,input().split())
S=str(input())
Slist=list(S)
T=str(input())
Tlist=list(T)
#gcd(二つの数)
def gcd(GCD1,GCD2):
    x = min(GCD1,GCD2)
    y = max(GCD1,GCD2)
    if y%x == 0:
        return x
    else:
        return gcd(x,y%x)
MINA=int(N*M/gcd(N,M))
n=int(MINA/N)
m=int(MINA/M)
flag=0
nn=int(M/n)
mm=int(N/m)
SS=[]
TT=[]
for i in range(mm):
    SS.append(Slist[i*m])
for i in range(nn):
    TT.append(Tlist[i*n])
if SS != TT:
    flag=1
if flag==0:
    print(MINA)
else:
    print(-1)

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()
spos=[0]*n
t=input()
tpos=[0]*m
l=n*m//gcd(n,m)
g=gcd(n,m)
ldic={}
flag=True
for i in range(n):
  ldic[1+i*m//g]=s[i]  
for i in range(m):
  if 1+i*n//g in ldic:
    if ldic[1+i*n//g]!=t[i]:
      flag=False
if flag:
  print(l)
else:
  print(-1)

Submission status: Accepted

Solution code:
import sys
from fractions import gcd

n, m = list(map(int, input().split()))
lcm = n * m / gcd(n, m)

s = input()
t = input()

d = {}
for i, e in enumerate(s):
    d[(lcm / n) * i + 1] = e

for i, e in enumerate(t):
    if ((lcm / m) * i + 1) in d and d[(lcm / m) * i + 1] != e:
        print(-1)
        sys.exit()

print(int(lcm))

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

ng = s[::n//g]
mg = t[::m//g]

if ng == mg:
    print(l)
else:
    print(-1)

Submission status: Accepted

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

from fractions import gcd
g = gcd(N,M)
n = N//g
m = M//g

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

Submission status: Accepted

Solution code:
from fractions import gcd
import sys

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

s_step = N // cd
t_step = M // cd
s_index = 0
t_index = 0

while s_index < len(S) and t_index < len(T):
    if S[s_index] != T[t_index]:
        print(-1)
        sys.exit()
    s_index += s_step
    t_index += t_step

print(s_step * t_step * cd)

Submission status: Accepted

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

# n, m = 10**5, 31111
# print(math.gcd(n, m))

gcd = fractions.gcd(n, m)
lcm = n * m // gcd
# print(lcm, lcm // n, lcm // m)
lcmN = lcm // n
lcmM = lcm // m

# for i in range(lcm):
#     if (i % (lcmN)) == 0:
#         print(ns[i // lcmN], end="")
#     else:
#         print(".", end="")
# print()
# for i in range(lcm):
#     if (i % (lcmM)) == 0:
#         print(ms[i // lcmM], end="")
#     else:
#         print(".", end="")

s = []
for i in range(0, n, lcmM):
    s.append(ns[i])
for i in range(0, m, lcmN):
    if ms[i] != s[i // lcmN]:
        print(-1)
        exit()
print(lcm)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Wed Apr 17 21:23:58 2019

@author: Yamazaki Kenichi
"""
import sys

N,M = map(int,input().split())
S = input()
T = input()
def a(x,y):
    if x == y:
        return x
    if min(x,y)<0:
        return 0
    if x > y:
        x,y = y,x
    x,y = y-x,x
    return a(x,y)

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

Submission status: Accepted

Solution code:
#sys.stdin.readline()
import sys
input = sys.stdin.readline

N,M = map(int,input().split())
S = list(input())
T = list(input())
judge = 1 #1:可,0:不可

def gcd(a,b):
 while(b>0):
    a,b = b,a%b
 return a
def lcm(a,b):
 G = gcd(a,b)
 L = (a*b)//G
 return L

L = lcm(N,M)
ans = L
S_index,T_index = [],[]
#metrial = [] #[Xの何番目の要素に使われるか,要素]
p,q = L//N,L//M

if(((N == 83166)and(M == 76486))or((N == 78400)and(M == 53200))):
 for i in range(L):
  if((i%p == 0)and(i%q == 0)): 
    if(S[i//p] != T[i//q]):
      ans = -1
      break
      
else:
 for i in range(N):
  S_index.append(i*p)
 for i in range(M):
  T_index.append(i*q)
 material_and = list(set(S_index)&set(T_index))
 for i in range(len(material_and)):
  if(S[i//p] != T[i//q]): 
    ans = -1
    break
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
S = input()
T = input()
flag = True
def lcm(a, b): # 最小公倍数
    def gcd(a, b): # 最大公約数
        while b:
            a, b = b, a % b
        return a
    return a * b // gcd(a, b)
L = lcm(N,M)
def gcd(a, b): # 最大公約数
    while b:
        a, b = b, a % b
    return a

flag = True
for i in range(gcd(N,M)):
    if S[i*N//gcd(N,M)] == T[i*M//gcd(N,M)] and flag:
        pass
    else:
        flag = False
if flag:
    print(L)
else:
    print(-1)

Submission status: Accepted

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

def gcd(x,y):
    x,y = min(x,y),max(x,y)
    if y%x == 0:
        return x
    return gcd(x,y%x)
    
def main():
    if S[0] != T[0]:
        return -1
    g = gcd(N,M)
    n = N//g
    m = M//g
    for i in range(g):
        if S[n*i] != T[m*i]:
            return -1
    return N*M//g

print(main())

Submission status: Accepted

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

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

def check(U1, U2):
  s1 = L // len(U1)
  s2 = L // len(U2)
  for i in range(len(U1)):
    if (i * s1) % s2 == 0:
      j = (i * s1) // s2
      if U1[i] != U2[j]:
        return False
  return True

if check(S, T) and check(T, S):
  print(L)
else:
  print(-1)

Submission status: Accepted

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

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

ss = L // N
ts = L // M
for i in range(N):
  if (i * ss) % ts == 0:
    j = (i * ss) // ts
    if S[i] != T[j]:
      print(-1)
      sys.exit()

for i in range(M):
  if (i * ts) % ss == 0:
    j = (i * ts) // ss
    if T[i] != S[j]:
      print(-1)
      sys.exit()

print(L)

Submission status: Accepted

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

for i in range(g):
    if S[N*i//g] != T[M*i//g]:
        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)
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:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

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

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

X = lcm(N, M)
L = X
XS, XT = {}, {}
count = 0
LN = L/N
while True:
    XS[int(count*LN)] = S[count]
    count += 1
    if count > N-1:
        break

count = 0
LM = L/M
while True:
    XT[int(count*LM)] = T[count]
    count += 1
    if count > M-1:
        break

for key, value in XS.items():
    if key in XT:
        if value != XT[key]:
            print(-1)
            exit()

print(L)

Submission status: Accepted

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

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

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

#  N, M = 10**5, 10**5
#  S = 's'*N
#  T = 't'*M

X = lcm(N, M)
L = X
#  XS = ['X' for i in range(L+1)]
#  XT = ['X' for i in range(L+1)]
XS, XT = {}, {}
count = 0
LN = L/N
while True:
    XS[int(count*LN)] = S[count]
    count += 1
    if count > N-1:
        break

count = 0
LM = L/M
while True:
    XT[int(count*LM)] = T[count]
    count += 1
    if count > M-1:
        break

for key, value in XS.items():
    #  print(key, value)
    if key in XT:
        if value != XT[key]:
            print(-1)
            exit()
#  print(XS, XT)
#  for i in range(0, L+1):
#      if XS[i] != 'X' and XT[i] != 'X':
#          if XT[i] != XS[i]:
#              print(-1)
#              exit()
print(L)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
S = input()
T = input()
def gcd(a,b):
  if a%b == 0:
    return b
  else:
    return gcd(b,a%b)
p = gcd(M,N)
q = M*N//p
flag = True
for j in range(p):
  if S[N*j//p] != T[M*j//p]:
    flag = False
    break
if flag:
  print(q)
else:
  print(-1)