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: Time Limit Exceeded

Solution code:
def lcm(x, y):
   """This function takes two
   integers and returns the L.C.M."""

   # choose the greater number
   if x > y:
       greater = x
   else:
       greater = y

   while(True):
       if((greater % x == 0) and (greater % y == 0)):
           lcm = greater
           break
       greater += 1

   return lcm

N, M = [int(i) for i in input().split()]
S = input()
T = input()
finallength = lcm(N, M)
splace = ['' for i in range(finallength)]
tplace = ['' for i in range(finallength)]
counter = 0
for i in range(0,finallength, finallength //N):
    splace[i] = S[counter]
    counter += 1
counter = 0
for i in range(0,finallength, finallength //M):
    tplace[i] = T[counter]
    counter += 1
for i in range(finallength):
    if splace[i] != '' and tplace[i] != '':
        if splace[i] != tplace[i]:
            print(-1)
            break
else:
    print(finallength)

Submission status: Time Limit Exceeded

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)

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


N, M = [int(_) for _ in input().split()]
S = input()
T = input()

L = lcm(N, M)


X = ['_' for i in range(L)]

j = 0
for i in range(0, L, L // N):
    X[i] = S[j]
    j += 1

j = 0
for i in range(0, L, L // M):
    if X[i] != '_' and X[i] != T[j]:
        print("-1")
        exit()
    X[i] = T[j]
    j += 1

print(L)

Submission status: Time Limit Exceeded

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


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


for i in range(k, n * m + 1, k):
    g = i * i // n // m // gcd(i // n, i // m)
    flag = True
    for c in range(0,i,g):
        if S[c * n // i] != T[c * m // i]:
            flag = False
            break
    if flag:
        print(i)
        exit()
print(-1)

Submission status: Time Limit Exceeded

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

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

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

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


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

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

ans = ''
for i in range(lcm_NM):
    if i % lcm_NM == 0:
        ans += S[i // M]
    elif i % M == 0:
        ans += S[i // M]
    elif i % N == 0:
        ans += T[i // N]
    else:
        ans += 'a'
print(len(ans))

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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


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

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

for i in range(l):
    if i % nn == 0 and i % mm == 0:
        if i // nn > n:
            continue
        if i // mm > m:
            continue
        if s[i // nn] != t[i // mm]:
            ok = False

print(l if ok else -1)

Submission status: Time Limit Exceeded

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)

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


N, M = [int(_) for _ in input().split()]
S = input()
T = input()

L = lcm(N, M)


X = ['_' for i in range(L)]

j = 0
for i in range(L):
    if i % (L // N) == 0:
        X[i] = S[j]
        j += 1

j = 0
for i in range(L):
    if i % (L // M) == 0:
        if X[i] != '_' and X[i] != T[j]:
            print("-1")
            exit()
        X[i] = T[j]
        j += 1

print(L)

Submission status: Time Limit Exceeded

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


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


for i in range(k, n * m + 1, k):
    ss = {a * (i // n) for a in range(n)}
    tt = {a * (i // m) for a in range(m)}
    st = ss & tt
    flag = True
    for c in st:
        if S[c * n // i] != T[c * m // i]:
            flag = False
            break
    if flag:
        print(i)
        exit()
print(-1)

Submission status: Time Limit Exceeded

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

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

renl=lcm(n,m)
a=['0' for _ in range(renl)]
b=['0' for _ in range(renl)]
for i in range(n):
    a[i*renl//n]=s[i]
for i in range(m):
    b[i*renl//m]=t[i]
for i in range(renl):
    if a[i]==b[i] or a[i]=='0' or b[i]=='0':
        continue
    else:
        print('-1')
        exit(0)
print(renl)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
n,m = map(int, input().split())
s = input()
t = input()

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

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

l = lcm(n,m)
ls = ["." for _ in range(l)]

for i in range(n):
    ls[i*l//n] = s[i]
for i in range(m):
    if ls[i*l//m]!="." and ls[i*l//m]!=t[i]:
        print(-1)
        exit()
print(l)

Submission status: Time Limit Exceeded

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

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


for i in range(k, n * m + 1, k):
    ss = {a*(i//n) for a in range(n)}
    tt = {a*(i//m) for a in range(m)}
    st = ss & tt
    x = ''.join(S[c//(i//n)]for c in st)
    y = ''.join(T[c//(i//m)]for c in st)
    if x == y:
        print(i)
        exit()
print(-1)

Submission status: Time Limit Exceeded

Solution code:
def gcd(x,y):
    a=max(x,y)
    b=min(x,y)
    if a%b==0:
        return b
    else:
        return gcd(a%b,b)
def lcm(x,y):
    return (x*y)//gcd(x,y)
N,M=map(int,input().split())
S=input()
T=input()
X=lcm(N,M)
U=["" for i in range(X)]
A=X//N
B=X//M
for i in range(N):
    U[i*A]=S[i]
for i in range(M):
    if U[i*B]!="" and U[i*B]!=T[i]:
        print(-1)
        exit()
    else:
        U[i*B]=T[i]
print(X)

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

if all([S[i*N//L] == T[i*M//L] for i in range(L)]):
    print(lcm(N,M))
else:
    print('-1')

Submission status: Accepted

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

#a,bの最小公倍数
def lcm(a, b):
	return a * b // gcd (a, b)
n,m = map(int,input().split())
s = input()
t = input()
mx = max(n,m)
mn = min(n,m)
if mx / mn % 1 == 0:
    c = mx//mn
    if mn == len(s):
        if s == t[::c]:
            print(t[::c])
            print(mx)
        else:
            print(-1)
    else:
        if t == s[::c]:
            print(s[::c])
            print(mx)
        else:
            print(-1)
else:
    num = lcm(n,m)
    mmx = num // mx
    mmn = num // mn
    ber = lcm(mmx,mmn)
    if mn == len(s):
        if s[::ber//mmn] == t[::ber//mmx]:
            print(num)
        else:
            print(-1)
    else:
        if s[::ber//mmx] == t[::ber//mmn]:
            print(num)
        else:
            print(-1)

Submission status: Accepted

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

Submission status: Accepted

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

# 良い文字列が作れるなら、答えはLCM(n, m)となる
gcd = math.gcd(n, m)
if s[::n//gcd] == t[::m//gcd]:
    print(n * m // gcd)
else:
    print(-1)

Submission status: Accepted

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

# 良い文字列が作れるなら、答えはLCM(n, m)となる
lcm = n * m // math.gcd(n, m)

x = {}
for i,c in enumerate(s):
    # (pos, char)
    x[lcm//n*i] = c

for i,c in enumerate(t):
    # (pos, char)
    pos, char = lcm//m*i, c
    if pos in x and x[pos] != char:
        print(-1)
        exit()

print(lcm)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
from itertools import permutations
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)
lcm = N * M // gcd(N, M)
# SとTそれぞれindexが何個進むとlcm番目の文字が出現するか求める
si = lcm // M
ti = lcm // N

i = 0
j = 0
ok = True
while i < N and j < M:
    if S[i] != T[j]:
        ok = False
        break
    i += si
    j += ti
if ok:
    print(lcm)
else:
    print(-1)

Submission status: Accepted

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

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

def gcd(x, y):
    if x < y:
        x, y = y, x

    if y == 0:
        return x

    else:
        return gcd(y, x % y)

nm = gcd(N, M)

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

else:
    sp = N // nm
    tp = M // nm

    si = 0
    ti = 0

    ans = True

    while (si < N and ti < M):
        if S[si] == T[ti]:
            si += sp
            ti += tp
        else:
            ans = False
            break

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from collections import defaultdict
import math
n,m = map(int, input().split())
s = input()
t = input()

ans = int((n*m)/math.gcd(n,m))
d = defaultdict(int)
if n > m:
  for i in range(n):
    if i == 0:
      d[1] = s[i]
    else:
      d[i*int(ans/n)+1] = s[i]
  ng = 0
  for i in range(m):
    if i == 0:
      if d[1] != t[i]:
        ng += 1
    else:
      if d[i*int(ans/m)+1] != 0 and d[i*int(ans/m)+1] != t[i]:
        ng += 1
else:
  for i in range(m):
    if i == 0:
      d[1] = t[i]
    else:
      d[i*int(ans/m)+1] = t[i]
  ng = 0
  for i in range(n):
    if i == 0:
      if d[1] != s[i]:
        ng += 1
    else:
      if d[i*int(ans/n)+1] != 0 and d[i*int(ans/n)+1] != s[i]:
        ng += 1
if ng > 0:
  print (-1)
else:
  print (ans)

Submission status: Accepted

Solution code:
import math

class common_function():
    """
        1. よく使いそうで予め用意しておいた変数をまとめた
        2. よく使いそうな関数群をまとめた
    """
    def lcm(self, x:int, y:int):
        """
            最小公倍数を返すメソッド
            math をインポートする
        """
        return (x * y) // math.gcd(x, y)
        

def main():
    common = common_function()
    N, M = map(int, input().split())
    S = input()
    T = input()
    lengthX = common.lcm(N, M)
    XdivS = lengthX//N
    XdivT = lengthX//M
    X = []
    for i in range(N):
        j = XdivS*i
        X.append((j, S[i]))
    X.sort(key=lambda x: x[0], reverse=True)
    
    k, x = X.pop()
    for i in range(M):
        j = XdivT*i
        for a in range(lengthX):
            if len(X) == 0:
                break
            if k < j:
                k, x = X.pop()
            else:
                break
        if k == j:
            if x != T[i]:
                print(-1)
                return
    print(lengthX)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

g = gcd(n, m)
ans = n*m//g

"""
最小公倍数の長さで収まらない場合は、何をやってもダメ
"""
for i in range(g):
    if not s[i*n//g] == t[i*m//g]:
        print(-1)
        exit(0)
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=input() ;a=len(s)
t=input() ;b=len(t)
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)
L=lcm(len(s),len(t))

d={}
now=0
for i in range(0,L,L//a):
    d[i]=s[now]
    now+=1
now=0
for j in range(0,L,L//b):
    if d.get(j, t[now])!=t[now]:
        print(-1);exit()
    now+=1
print(L)

Submission status: Accepted

Solution code:
import sys, math
from functools import lru_cache
from collections import defaultdict
from decimal import Decimal
sys.setrecursionlimit(10**9)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

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

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

def main():
    N, M = mi()
    S, T = [list(input()), list(input())]

    g = math.gcd(N, M)
    l = N*M//g

    for i in range(g):
        if not (S[N//g*i] == T[M//g*i]):
            print(-1)
            return

    print(l)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from math import gcd
n,m=map(int,input().split())
s=input()
t=input()
res=n*m//gcd(n,m)
a=m//gcd(n,m)
b=n//gcd(n,m)
if n>=m:
  for i in range(m):
    if (i*b)%a==0:
      if s[(i*b)//a]!=t[i]:
        print(-1)
        exit()
else:
  for i in range(n):
    if (i*a)%b==0:
      if s[i]!=t[(i*a)//b]:
        print(-1)
        exit()
print(res)

Submission status: Accepted

Solution code:
#66 A - Two Abbreviations
import math
N,M = map(int,input().split())
S = input()
T = input()

GCD = math.gcd(N,M)
L = N*M//GCD

dist_N = L//N
dist_M = L//M

# 同じ位置に書く文字は最大公約数 + 1 だけ存在する
for i in range(GCD):
    # S の s 文字目と T の t 文字目が同じ位置に来る
    s = dist_M * i
    t = dist_N * i
    if S[s] != T[t]:
        ans = -1
        break
else:
    ans = L
print(ans)

Submission status: Accepted

Solution code:
from math import gcd
n,m = map(int,input().split())
z = n * m // gcd(n,m)
s = input()
t = input()
n = z // n
m = z // m
x = 0
y = 0
i = 0
j = 0
while x < z and y < z:
    if x > y:
        y += m
        j += 1
    elif x < y:
        x += n
        i += 1
    else:
        if s[i] != t[j]:
            print(-1)
            exit(0)
        x += n
        y += m
        i += 1
        j += 1
print(z)

Submission status: Accepted

Solution code:
import sys
from sys import exit
from collections import deque
from bisect import bisect_left, bisect_right, insort_left, insort_right #func(リスト,値)
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from math import *

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x):
        self.setdefault(x,0)
        self[x] += 1

N,M = mint()
S,T = input(),input()
l,g = lcm(N,M),gcd(N,M)
ans = True
for i in range(g):
    if S[i*l//M]!=T[i*l//N]:
        ans = False
        break
print(l if ans else -1)

Submission status: Accepted

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

Submission status: Accepted

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


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


def main():
    n, m = map(int, input().split())
    s = input()
    t = input()
    ans = lcm(n, m)
    ln = ans // n
    lm = ans // m
    l = lcm(ln, lm)
    i = 0
    while i * l // ln < n and i * l // lm < m:
        if s[i * l // ln] != t[i * l // lm]:
            ans = -1
            break
        i += 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
N,M = map(int,input().split())
S = input()
T = input()
L = N * M // math.gcd(N,M)
NN = L // N
MM = L // M

for i in range(10**6):
    if MM*i > len(S)-1 or NN*i > len(T)-1:
        break
    if S[i*MM] != T[i*NN]:
        print(-1)
        exit()
print(L)

Submission status: Accepted

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

Submission status: Accepted

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

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

# lcmで異なる文字が重なるようならダメ。そうでなければOK


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


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


l = lcm(N, M)

s = l // N
t = l // M
# print(f'{s=}, {t=}')
S_set = set([s * i for i in range(N)])
T_set = set([t * i for i in range(M)])

_set = S_set & T_set
# print(f'{S_set=}, {T_set=}, {_set=}')

for i in _set:
    if S[i // s] != T[i // t]:
        print(-1)
        exit()
print(l)
# a c p |
# a  e  |

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    from functools import reduce
    def lcm_base(n1,n2):
        return (n1*n2)//math.gcd(n1,n2)
    def lcm(*numbers):
        return reduce(lcm_base, numbers)
    n,m = LI()
    s = S()
    t = S()
    l1 = lcm(n,m)
    s_unit = l1//n
    t_unit = l1//m
    l2 = lcm(s_unit, t_unit)
    time = (l1-1)//l2+1
    itr = [l2*i for i in range(time)]
    ans = l1

    for i in itr:
        si = i//s_unit
        ti = i//t_unit
        if s[si] != t[ti]:
            ans = -1

    print(ans)

main()

Submission status: Accepted

Solution code:
import sys
import math


inint = lambda: int(sys.stdin.readline())
inintm = lambda: map(int, sys.stdin.readline().split())
inintl = lambda: list(inintm())
instrm = lambda: map(str, sys.stdin.readline().split())
instrl = lambda: list(instrm())

n, m = inintm()
s = input()
t = input()

c = {}

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

lcm_num = lcm(n,m)

for i in range(n):
    c[i*m + 1] = s[i]

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

print(lcm_num)

Submission status: Accepted

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

import sys
# sys.setrecursionlimit(100000)


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


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]
# Greatest Common Divisor(Euclidean algorithm)


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


# Least Common Multiple
def lcm(x: int, y: int) -> int:
    _gcd = gcd(x, y)
    return (x * y) // _gcd


def main():
    n, m = input_int_list()
    _gcd = gcd(m, n)
    size = lcm(m, n)
    S = input()
    T = input()
    if S[::n // _gcd] == T[::m // _gcd]:
        print(size)
    else:
        print(-1)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from math import gcd
def main():
    n, m = map(int, input().split())
    s = tuple(input())
    t = tuple(input())

    if n > m:
        l1 = n
        l2 = m
        s1 = s
        s2 = t
    else:
        l1 = m
        l2 = n
        s1 = t
        s2 = s

    if s[0] != t[0]:
        r = -1
    elif n == m:
        if s == t:
            r = n
        else:
            r = -1
    elif n % m == 0 or m % n == 0:
        ld = l1 // l2
        for i1 in range(1, l2):
            if s2[i1] != s1[i1*ld]:
                r = -1
                break
        else:
            r = l1
    else:
        l = (n * m) // gcd(n, m)
        # x = [0] * l
        ld1 = l // l1
        ld2 = l // l2
        cnt = 1
        r = l
        while cnt < l1:
            cnt2 = cnt * ld1
            if cnt2 % ld2 == 0:
                if s1[cnt] != s2[cnt2 // ld2]:
                    r = -1
                    break
            cnt += 1
    print(r)

if __name__ == '__main__':
    main()

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)
d = {}
s = set()
for i in range(N):
    d[str(i * (L // N))] = S[i]
    s.add(str(i * (L // N)))

for i in range(M):
    key = str(i * (L // M))
    if key in s:
        if d[key] != T[i]:
            print(-1)
            exit()
print(L)

Submission status: Accepted

Solution code:
import math
import sys
n, m = map(int, input().split())
s = list(input())
t = list(input())
a = (n*m)//math.gcd(n, m)
b0 = [i*(a//n)+1 for i in range(n)]
b1 = [i*(a//m)+1 for i in range(m)]
b2 = set(b0)
b3 = set(b1)

for j, i in enumerate(b0):
    if i in b3:
        if s[j] != t[b1.index(i)]:
            print(-1)
            sys.exit()
            
for j, i in enumerate(b1):
    if i in b2:
        if s[b0.index(i)] != t[j]:
            print(-1)
            sys.exit()
print(a)

Submission status: Accepted

Solution code:
import math

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

x = math.gcd(n,m)
ans = n*m//x
n = n//x
m = m//x

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from math import gcd as g
n,m=map(int,input().split())
s=input()
t=input()
k=(a:=(N:=(l:=n*m//g(n,m))//n))*(b:=(M:=l//m))//g(a,b)
print(-1 if s[0]!=t[0] or (l==n and s!=t*N) or (l==m and t!=s*M) or s[::b]!=t[::a] else l)

Submission status: Accepted

Solution code:
# 02
import sys
import math


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


INF = float('inf')


n, m = LI()
s = S()
t = S()

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

Submission status: Accepted

Solution code:
from math import gcd

n, m = map(int, input().split())
g = gcd(n, m)
s = input()
t = input()
f = True
for i in range(g):
    a = i * n // g
    b = i * m // g
    f &= (s[a] == t[b])

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

Submission status: Accepted

Solution code:
from math import gcd

def lcm(a, b):
    _a = a
    while a % b != 0:
        a += _a
    return a


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


N, M = map(int, input().split())
#N = max(_N, _M)
#M = min(_N, _M)
S = input()
T = input()
L = N * M // gcd(N, M)
#print(L)
s_now = 0
t_now = 0
while True:
    if S[s_now] != T[t_now]:
        print(-1)
        break
    s_now += L//M
    t_now += L//N
    if s_now >= N or t_now >= M:
        print(L)
        break
#print(L//M, L//N)
#print(N//gcd(N, M), M//gcd(N, M))

Submission status: Accepted

Solution code:
import math

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

g = math.gcd(N, M)
lcm = N * M // g
flg = True
N //= g
M //= g
for i in range(g):
    if S[i*N] != T[i*M]:
        flg = False
        break
if flg:
    print(lcm)
else:
    print(-1)

Submission status: Accepted

Solution code:
import math

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

g = math.gcd(n, m)
n //= g
m //= g

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

Submission status: Accepted

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


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


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


l = lcm(len(s), len(t))
x = {}  # これふつうにリストだとREになるのマジで謎なんだけど
for i in range(0, len(s)):
    x[i * (l // len(s))] = s[i]
for i in range(0, len(t)):
    if i * (l // len(t)) not in x:
        continue
    else:
        if x[i * (l // len(t))] != t[i]:
            print(-1)
            exit()
print(l)

Submission status: Accepted

Solution code:
from math import gcd
n, m = map(int, input().split())
s = list(input())
t = list(input())
g = gcd(n, m)
ans = n*m//g
sp_a, sp_b = m//g, n//g
jud = True
for i in range(ans//sp_a):
    if i*sp_a % sp_b == 0:
        if s[i % n] != t[i*sp_a//sp_b]:
            jud = False

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

Submission status: Accepted

Solution code:
from math import gcd

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

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

cnt = (l // m) * (l // n)
a = [i * l // m for i in range(l // cnt)]
b = [i * l // n for i in range(l // cnt)]

for i in range(l // cnt):
    a1 = a[i]
    b1 = b[i]
    if s[a1] == t[b1]:
        pass
    else:
        print(-1)
        exit()

print(l)

Submission status: Accepted

Solution code:
import math

n,m = map(int,input().split())
a = input()
b = input()
g = math.gcd(n,m)
l = (n*m)//g
d = {}
for i in range(n):
    d[i*(l//n)] = a[i]
for i in range(m):
    if i*(l//m) in d:
        if d[i*(l//m)] != b[i]:
            print(-1)
            exit()
print(l)

Submission status: Accepted

Solution code:
import math

n,m = map(int,input().split())
a = input()
b = input()
if a[0] != b[0]:
    print(-1)
    exit()

g = math.gcd(n,m)
if g == 1:
    print(n*m//g)
else:
    l = (n*m)//g
    d = {}
    for i in range(n):
        d[i*(l//n)] = a[i]
    for i in range(m):
        if i*(l//m) in d:
            if d[i*(l//m)] != b[i]:
                print(-1)
                exit()
    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)
L=(N*M)//G

P=L//N
Q=L//M

A=range(0,L,P)
B=range(0,L,Q)

F=True
for k in A:
    if k in B:
        F&=S[k//P]==T[k//Q]
if F:
    print(L)
else:
    print(-1)

Submission status: Accepted

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

Submission status: Accepted

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

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

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

nd = l//n
md = l//m

common = nd*md//gcd(nd,md)
nc = common//nd
mc = common//md

sol = True
for i in range(0, l, common):
    ind = i//common
    if s[ind * nc] != t[ind * mc]:
        sol = False
        break

print(l if sol else -1)

Submission status: Accepted

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

print(gn*gm*g)

Submission status: Accepted

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

NMgcd = math.gcd(N,M)
Leng  = N*M//NMgcd
Flag  = True
SList = [S[Nk] for Nk in range(0,N) if Nk%(N//NMgcd)==0]

for Mk in range(0,len(SList)):
    if SList[Mk]!=T[Mk*(M//NMgcd)]:
        Flag = False
        break
if Flag:
    print(Leng)
else:
    print(-1)