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
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

from collections import defaultdict
import math
n,m = map(int, input().split())
s = input()
t = input()
g = math.gcd(n,m)
d = defaultdict(list)
for i in range(n):
    ind = i*(m//g)
    d[ind].append(s[i])
for i in range(m):
    ind = i*(n//g)
    d[ind].append(t[i])
for k,v in d.items():
    if v and not all(item==v[0] for item in v):
        ans = -1
        break
else:
    ans = n*m//g
print(ans)

Submission status: Accepted

Solution code:
import math
def lcm(x, y):
    return (x * y) // math.gcd(x, y)
N,M = map(int,input().split())
S = input()
T = input()

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

Submission status: Accepted

Solution code:
def gcd(a,b):
    if(a%b!=0):
        return gcd(b,a%b)
    else:
        return b
def lcm(a,b):
    return (a*b//(gcd(a,b)))
def main3():
    n,m=map(int, input().split())
    s=input()
    t=input()
    if(n>m):
        s1 = t
        t1 = s
    else:
        s1 = s
        t1 = t
    l = (lcm(n,m))
    l_n = l//n
    l_m = l//m
    i = 0
    ind_min = []
    ind_max = []
    while(i<min(n,m)):
        ind_min.append(i*max(l_n,l_m)+1)
        i+=1
    i = 0
    while(i<max(n,m)):
        ind_max.append(i*min(l_n,l_m)+1)
        i+=1

    ind_max_d = {k:i for i,k in enumerate(ind_max)}

    for i in range(len(ind_min)):
        if(ind_min[i] in ind_max_d):
            if(s1[i] != t1[ind_max_d[ind_min[i]]]):
                print(-1)
                exit()
    print(l)



if __name__ == '__main__':
    main3()

Submission status: Accepted

Solution code:
N, M=map(int, input().split())
s=input()
t=input()
from math import gcd

g=gcd(N,M)

if g==1:
  ans=(N*M)//g
else:
  n=N//g
  m=M//g
  import numpy as np
  pn=np.arange(m, M, m)
  qm=np.arange(n, N, n)
  ans=(N*M)//g
  for i in range(len(pn)):
    if s[qm[i]]!=t[pn[i]]:
      ans=-1
      break
if s[0]!=t[0]:
  ans=-1
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
 
N,M = I()
S = list(s())
T = list(s())
n = lcm(N,M)
l = (N-1)//(n//M)
for i in range(l+1):
    if S[i*(n//M)] != T[i*(n//N)]:
        print(-1)
        exit()
print(n)

Submission status: Accepted

Solution code:
from math import gcd
N, M = map(int, input().split())
S = input()
T = input()
G = gcd(N, M)
 
for i in range(G):
    if S[i * N // G] != T[i * M // G]:
        print(-1)
        exit()
 
l = N * M // G
print(l)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from math import gcd
import numpy
N, M = map(int, input().split())
S = input()
T = input()
def func(m, n):
    return (m * n) // gcd(m, n)
ans = func(N, M)
var1 = ans//N
var2 = ans//M
for i in range(1, ans+1, var1*var2):
    varS = (i - 1) // var1
    varT = (i - 1) // var2
    if S[varS] != T[varT]:
        ans=-1
print(ans)

Submission status: Accepted

Solution code:
from math import gcd
N,M = map(int, input().split())
S = input()
T = input()
G = gcd(N,M)
for i in range (G):
  if S[N//G * i] != T[M//G * i]:
    print(-1)
    exit()
print(N//G * M//G * G)

Submission status: Accepted

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

# SとTがXの同じ部分を参照する際、それらが等しくなければならない
for i in range(G):
    # N/GやM/Gは必ず整数になるが、intにするために//で演算
    if S[i * N // G] != T[i * M // G]:
        print(-1)
        exit()

# 最小公倍数、lcm(N,M)は用意されていない
# 同様にintにするため//で演算
l = N * M // G
print(l)

Submission status: Accepted

Solution code:
from math import gcd

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

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

lc = lcm(N, M)

ss = lc//N
tt = lc//M

for i in range(1, lc+1, ss*tt):
    s_tmp = (i - 1) // ss
    t_tmp = (i - 1) // tt

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

print(lc)

Submission status: Accepted

Solution code:
import math


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


N, M = map(int, input().split())
S = input()
T = input()
L = lcm(N, M)
G = math.gcd(N, M)
for i in range(G):
    if S[N//G * i] != T[M//G * i]:
        print(-1)
        break
else:
    print(L)

Submission status: Accepted

Solution code:
from math import gcd
N,M = map(int, input().split())
S = input()
T = input()
G = gcd(N,M)
for i in range (G):
  if S[N//G * i] != T[M//G * i]:
    print(-1)
    exit()
print(N//G * M//G * G)

Submission status: Accepted

Solution code:
from math import gcd

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

g=gcd(n,m)

ng=n//g
mg=m//g

for i in range(0,g):
    if s[ng*i]!=t[mg*i]:
        print(-1)
        exit()
print(ng*mg*g)

Submission status: Accepted

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

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

lcm = N * M // math.gcd(N, M)
#1,(L/N) +1, 2*(L/N) +1..(N-1)*(L/N)+1
tekito =[]
for i in range(1,N):
  tekito.append(i*(lcm//N)+1)
tekitu =[]
for i in range(1,M):
  tekitu.append(i*(lcm//M)+1)

gattai = set(tekito) & set(tekitu) 
for k in gattai:
  i1 = (k-1) // (lcm//N)
  i2 = (k-1) // (lcm//M)
  if S[i1] != T[i2]:
    print(-1)
    exit()
print(lcm)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/agc028/tasks/agc028_a

# 問題からエスパーするとlcmが答えになる
# lcmで作れないならそれ以上伸ばしても絶対作れない
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def read_ints(): return list(map(int, read().split()))


from math import gcd


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


N, M = read_ints()
S = read()[:-1]
T = read()[:-1]

L = lcm(N, M)
# 衝突する文字は各文字数をgcdで割った文字ごとに出現する
s_step = N // gcd(N, M)
t_step = M // gcd(N, M)
print(L if S[::s_step] == T[::t_step] else -1)

Submission status: Accepted

Solution code:
import math

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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7

N,M = I()
S = list(s())
T = list(s())
n = lcm(N,M)
l = (N-1)//(n//M)
for i in range(l+1):
    if S[i*(n//M)] != T[i*(n//N)]:
        print(-1)
        exit()
print(n)

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from math import gcd
def resolve():
    fixed = {}
    n, m = map(int, input().split())
    S = input()
    T = input()
    l = n // gcd(n, m) * m
    for i in range(n):
        fixed[i * l // n] = S[i]
    for j in range(m):
        if not j * l // m in fixed:
            continue
        if fixed[j * l // m] != T[j]:
            print(-1)
            return
    print(l)
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

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

    lcm = N*M//gcd(N,M)
    
    x = lcm//N
    y = lcm//M
    
    ans = lcm
    for i in range(N):
        j = x * i
        if j%y == 0:
            if S[i] != T[j//y]:
                ans = -1
                break
    
    for j in range(M):
        i = y * j
        if i%x == 0:
            if S[i//x] != T[j]:
                ans = -1
                break
    print(ans)  
if __name__ == '__main__':
    main()

Submission status: Accepted

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

def gcd(x, y):
    while y:
        x, y = y, x % y
    return x

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

g = gcd(n, m)
bl = True
for k in range(g):
    i, j = k * n // g, k * m // g
    if s[i] != t[j]: # s[i] != s[j] にしてた...
        bl = False

print(lcm(n, m)) if bl else print('-1')

Submission status: Accepted

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

N, M = MAP()

S = input()
T = input()

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

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

Submission status: Accepted

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

N, M = MAP()

S = input()
T = input()

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

G = gcd(N, M)

n = N//G
m = M//G

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

Submission status: Accepted

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

from fractions import gcd

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

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

ans=lcm
# sについて
dn={}
for i in range(n):
    if i==0:
        dn[1]=s[i]
    else:
        dn[i*int((lcm)/n) +1]=s[i]

for j in range(m):
    if j==0:
        continue
    else:
        k = j*int(lcm/m) + 1

        if k in dn:
            if dn[k]!=t[j]:
                ans=-1
        else:
            dn[k]=t[j]

print(ans)

Submission status: Accepted

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
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 LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

# GCD -- START --
def gcd(x,y):
  while y:
    x,y=y,x%y
  return x
# GCD --- END ---

# LCM -- START --
def lcm(x,y):
  return x*y//gcd(x,y)
# LCM --- END ---

def main():
  n,m=LI()
  s=S()
  t=S()
  a=lcm(n,m)

  x={}
  for i in range(n):
    x[i*(a//n)]=s[i]

  # print(x)

  for i in range(m):
    if i*(a//m) in x:
      if t[i]!=x[i*(a//m)]:
        return -1

  return a

# main()
print(main())

Submission status: Accepted

Solution code:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import deque
import pprint

inf = 10**18
mod = 10**9+7

n,m = map(int, input().split())
s = input()
t = input()
f=fractions.gcd(n,m)           #最大公約数
f2=n*m//f                          #最小公倍数


x = f2//n
y = f2//m

for i in range(n):
    if (x*i)%y==0:
        if s[i] != t[x*i//y]:
            print(-1)
            sys.exit()
print(f2)

Submission status: Accepted

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


def my_lcm(a, b):
    cum = a * b
    if a > b:
        a, b = b, a
    while a != 0:
        a, b = b % a, a
    # b がgcd になっている
    return cum // b


ans = my_lcm(n, m)
s_idx = 0
t_idx = 0
while s_idx < n and t_idx < m:
    if s[s_idx] != t[t_idx]:
        print(-1)
        exit()
    else:
        a = s[s_idx] + t[t_idx]
        t_idx += ans // n
        s_idx += ans // m
print(ans)

Submission status: Accepted

Solution code:
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 = gcd(n,m)
ans = lcm(n,m)
for i in range(L):
    if not s[n//L*i] == t[m//L*i]:
        ans = -1
        break
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

from fractions import gcd   #for python3.4
#from math import gcd        #for python3.8

def lcm(a,b):
    G = gcd(a, b) #最大公約数
    L = (a//G)*b #最小公倍数
    return L

def main():
    N, M = map(int, input().split())
    S = input()
    T = input()
    L = lcm(N,M)
    if S[::L//M]==T[::L//N]:
        print(L)
    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()
flg = True

ans = N*M//gcd(N, M)
n = ans // N
m = ans // M
a = n*m//gcd(n, m)
nn = a // n
mm = a // m
for i in range(1, ans//a):
    if S[nn*i] != T[mm*i]:
        flg = False
if S[0] != T[0]:
    flg = False
if flg:
    print(ans)
else:
    print(-1)

Submission status: Accepted

Solution code:
import fractions

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

g = fractions.gcd(N,M)

L = g * (N // g) * (M // g)

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

Submission status: Accepted

Solution code:
import fractions

def lcm(x,y):
    return (x*y) // fractions.gcd(x, y)
    
x, y = map(int, input().split())
s = input()
t = input()

lc = lcm(x,y)

s_l = lc//x
t_l = lc//y

for i in range(y):
    if i%s_l == 0:
        if t[i] == s[i*t_l//s_l]:
            continue
        else:
            print(-1)
            break
else:
    print(lc)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import fractions

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

if N == M:
    print(N if S == T else -1)
else:
    G = fractions.gcd(N, M)
    L = N * M // G
    n = N // G
    m = M // G
    ans = True
    for k in range(G):
        if S[k * n] != T[k * m]:
            ans = False
            break
    print(L if ans else -1)

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

ans = True
for k in range(G):
    if S[k*n] != T[k*m]:
        ans = False
        break
print(L if ans else -1)

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

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

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

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

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

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N,M = IL()
S1 = S()
S2 = S()

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

for i in range(GCD):
  if S1[i*N//GCD] != S2[i*M//GCD]:
    print(-1)
    exit()
print(LCM)

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
n = N // G
m = M // G

ans = True
for k in range(G):
    if S[k * n] != T[k * m]:
        ans = False
        break
print(L if ans else -1)

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)
i = 0
j = 0
ans = l
while i < n or j < m:
    temp_n = i*l//n+1
    temp_m = j*l//m+1
    if temp_n == temp_m:
        if S[i] != T[j]:
            ans = -1
            break
        i += 1
        j += 1
    elif temp_m > temp_n:
        i += 1
    else:
        j += 1

print(ans)

Submission status: Accepted

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

cfac = fractions.gcd(N,M)

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

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/agc028/tasks/agc028_a

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

def gcd(x, y): #GCD
    # greatest_common_divisor
    if x < y:
        x, y = y, x
    if y == 0:
        return 0
    if x % y == 0:
        return y
    return gcd(y, x % y)

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

l = lcm(n, m)
d = gcd(n, m)
n //= d
m //= d

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

Submission status: Accepted

Solution code:
import sys
import fractions

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N, M = [int(x) for x in input().split()]
    S = input().strip()
    T = input().strip()

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

    dic = {}
    for i, s in enumerate(S):
        dic[(ans // N) * i + 1] = s

    for i, t in enumerate(T):
        if ((ans // M) * i + 1) in dic.keys():
            if dic[(ans // M) * i + 1] != t:
                print(-1)
                return

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

flag=True
import fractions
gcdnm=fractions.gcd(n,m)
lcmnm=(n*m)//gcdnm

nn=n//gcdnm
mm=m//gcdnm

for i in range(gcdnm):
    if S[i*nn]!=T[i*mm]:
        flag=False

if flag==True:
    print(lcmnm)
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys
from fractions import gcd

input = sys.stdin.readline


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


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

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

    ans = L
    i = 0
    while i < L // (n * m):
        if S[m * i] != T[n * i]:
            ans = -1
            break
        i += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import fractions

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

# 最小公倍数を求める
l = (N * M) // fractions.gcd(N, M)

ans = {1: S[0]}
for i in range(1, N):
    c_num = i*l//N+1
    ans[c_num] = S[i]

for i in range(M):
    if i == 1:
        if ans[1] != T[0]:
            print(-1)
            exit(0)

    c_num = i*l//M+1
    if c_num in ans:
        if ans[c_num] != T[i]:
            print(-1)
            exit(0)
    else:
        ans[c_num] = T[i]
print(l)

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

Submission status: Accepted

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

Submission status: Accepted

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

import sys

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


g = gcd(N, M)
sn = N//g
sm = M//g

ok = True
for k in range(0, g):
    a = k * sn
    b = k * sm
    if S[a] != T[b]:
        ok = False
        break

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

Submission status: Accepted

Solution code:
def main():
    import sys
    from collections import defaultdict
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline

    def gcd(a, b):
        if b == 0:
            return a
        return gcd(b, a % b)
    
    N, M = [int(x) for x in input().strip().split()]
    S = input().strip()
    T = input().strip()
    L = (N * M) // gcd(N, M)
    d = defaultdict(int)
    for n in range(N):
        d[L//N*n] = S[n]
    for m in range(M):
        if d[L//M*m] == 0 or d[L//M*m] == T[m]:
            continue
        else:
            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()
g = gcd(N, M)
N //= g
M //= g
for i in range(g):
    if S[i * N] != T[i * M]:
        print(-1)
        break
else:
    print(N * M * g)

Submission status: Accepted

Solution code:
from fractions import gcd


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


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

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

Submission status: Accepted

Solution code:
from fractions import gcd


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


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

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

for i in range(N):
    X[(L // N) * i] = S[i]

for i in range(M):
    if (L // M) * i in X and X[(L // M) * i] != T[i]:
        print(-1)
        exit()
print(L)

Submission status: Accepted

Solution code:
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
#from math import gcd
from fractions import gcd
n,m = iim()
s = input()
t = input()
num = gcd(n,m)
lcm = n*m//num
print(lcm if s[::n//num] == t[::m//num] else -1)

Submission status: Accepted

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

def gcd(v1, v2):
    if v2 == 0:
        return v1
    return gcd(v2, v1%v2)

def lcm(v1,v2):
    return v1 * v2 // gcd(v1,v2)

my_gcd = gcd(N,M)
s_ = S[::N//my_gcd]
t_ = T[::M//my_gcd]
if s_ == t_:
    print(lcm(N,M))
else:
    print(-1)

Submission status: Accepted

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

ans = lcm(n, m)

chk = {}

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

Submission status: Accepted

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

Submission status: Accepted

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

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

ans = f(n,m)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=str(input())
s=list(s)
t=str(input())
t=list(t)
ans=-1
if s[0]==t[0]:
  import fractions
  temp=len(s)*len(t)//fractions.gcd(len(s),len(t))
  k=fractions.gcd(len(s),len(t))
  count=1
  for i in range(1,k):
    if s[i*int(len(s)/k)]==t[i*int(len(t)/k)]:
      count=count+1
  if count==k:
    ans=temp
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from fractions import gcd

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

dic = {}
L = int((N*M) / gcd(N,M))
ans = L

for i in range(N):
  dic[int(i*(L/N)+1)] = i

key = set(dic.keys())
for i in range(M):
  if i*(L/M)+1 in key:
    if S[dic[int(i*(L/M)+1)]] == T[i]:continue
    else: 
      ans = -1
      break

  


print(ans)

Submission status: Accepted

Solution code:
i=input;n,m=map(int,i().split());g=m-max(a*n%m for a in range(m));print([n*m//g,-1][i()[::n//g]!=i()[::m//g]])

Submission status: Accepted

Solution code:
i=input;n,m=map(int,i().split());g=m-max(a*n%m for a in range(m));print(i()[::n//g]!=i()[::m//g]and-1or n*m//g)