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 math
N,M = (int(T) for T in input().split())
S = input()
T = input()

NMG = math.gcd(N,M)
Length = N*M//NMG
Flag   = True
SIndex = [Nk*(M//NMG) for Nk in range(0,N)]
SList  = list(S)

Count = 0
for Mk in range(0,M):
    if Mk%(M//NMG)==0:
        if SList[Count*(N//NMG)]!=T[Mk]:
            Flag = False
            break
        else:
            Count += 1
if Flag:
    print(Length)
else:
    print(-1)

Submission status: Accepted

Solution code:
import math
N, M = map(int, input().split())
S = list(input())
T = list(input())
lcm = (N * M) // math.gcd(N, M)
ans = lcm
Sp = lcm//N
Tp = lcm//M
lcmlcm = (Sp * Tp) // math.gcd(Sp, Tp)
owari = min(Sp*N, M*Tp)
for i in range(0, owari, lcmlcm):
    if S[i//Sp] != T[i//Tp]:
        ans = -1
        break
print(ans)

Submission status: Accepted

Solution code:
from math import gcd

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

lcm = N * M // gcd(N, M)
count = 1

result = -1


def check(answer_length, line, answer):
    for i in range(0, len(line)):
        idx = i * answer_length // len(line) + 1

        if idx in answer:
            if not answer[idx] == line[i]:
                return False
        else:
            if idx <= answer_length:
                answer[idx] = line[i]
            else:
                return False

    return True


answer = {}
max_str = max((M-1) * (lcm * count) // M + 1,
                  (N-1) * (lcm * count) // N + 1)

if check(lcm * count, S, answer):
    if check(lcm*count, T, answer):
        print(lcm*count)
        exit()

print(result)

Submission status: Accepted

Solution code:
import math
from functools import reduce


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


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


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

    L = lcm([N, M])
    ic, jc = 0, 0
    i, j = ic * L // N + 1, jc * L // M + 1
    ans = L
    while ic < N and jc < M:
        # print(i, j, ic, jc, S[ic], S[jc])
        if i == j:
            if S[ic] != T[jc]:
                ans = '-1'
                break
            ic += 1
            jc += 1
            i = ic * L // N + 1
            j = jc * L // M + 1
        elif i < j:
            ic += 1
            i = ic * L // N + 1
        elif i > j:
            jc += 1
            j = jc * L // M + 1
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import math
from functools import reduce


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


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


def make_divisors(n):
    lower_divisors, upper_divisors = [], []
    i = 1
    while i * i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n // i)
        i += 1
    return lower_divisors + upper_divisors[::-1]


def commonDivisors(x1, x2):
    cf = []
    for i in range(2, min(x1, x2) + 1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf


def solve():
    N, M = [int(x) for x in input().split()]
    S = input()
    T = input()
    # cdivs = commonDivisors(N, M)
    # ans_flag = True
    # print(cdivs)
    # for c in cdivs:
    #     if S[c - 1] != T[c - 1]:
    #         ans_flag = False
    # if ans_flag:
    #     print(lcm([N, M]))
    # else:
    #     print(-1)
    # N_divs = make_divisors(N)
    # M_divs = make_divisors(M)
    L = lcm([N, M])
    ic, jc = 0, 0
    i, j = ic * L // N + 1, jc * L // M + 1
    ans = L
    while ic < N and jc < M:
        # print(i, j, ic, jc, S[ic], S[jc])
        if i == j:
            if S[ic] != T[jc]:
                ans = '-1'
                break
            ic += 1
            jc += 1
            i = ic * L // N + 1
            j = jc * L // M + 1
        elif i < j:
            ic += 1
            i = ic * L // N + 1
        elif i > j:
            jc += 1
            j = jc * L // M + 1
    print(ans)
    # print(N_divs, M_divs)
    # return
    # ans_flag = True
    # for d in divs:
    #     if S[d] != T[d]:
    #         ans_flag = False
    # if ans_flag:
    #     print(lcm([N, M]))
    # else:
    #     print(-1)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import math
N,M = (int(T) for T in input().split())
S = input()
T = input()
Length = N*M//math.gcd(N,M)
Flag   = True
SIndex = [Nk*(Length//N) for Nk in range(0,N)]
SList  = list(S)
    
for Mk in range(0,M):
    if Mk%(Length//N)==0:
        MInd = SIndex.index(Mk*(Length//M))
        if SList[MInd]!=T[Mk]:
            Flag = False
            break
        
if Flag:
    print(Length)
else:
    print(-1)

Submission status: Accepted

Solution code:
import math

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

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

if ans:
    print(a*b*GCD)
else:
    print(-1)

Submission status: Accepted

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

if M > N:
	M, N = N, M
	S, T = T, S

import math
G = N*M//math.gcd(N, M)

A = []
B = []

C = N//math.gcd(N,M)
D = M//math.gcd(N,M)

for i in range (0, math.gcd(N,M)):
	if S[i*C] != T[i*D]:
		print(-1)
		exit()

print(G)

Submission status: Accepted

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

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

ds = L // N
dt = L // M
S = S[0::dt]
T = T[0::ds]

if S == T:
    print(L)
else:
    print(-1)

Submission status: Accepted

Solution code:
import math

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

if n == m:
    if s == t:
        print(n)
    else:
        print(-1)
    exit()

if m == 1:
    n,m = m,n
    s,t = t,s

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

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

n1 = lcm//n
m1 = lcm//m

lcm2 = n1 * m1 // math.gcd(n1, m1)
stepn = lcm2//n1
stepm = lcm2//m1

for i in range(0,10**5):
    if stepn*i > n-1 or stepm*i > m-1:
        print(lcm)
        break
    if s[stepn*i] != t[stepm*i]:
        print(-1)
        exit()

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M = mapint()
S = list(input())
T = list(input())
from math import gcd

leng = N*M//gcd(N, M)
step = (leng//N)*(leng//M)//gcd((leng//N), (leng//M))

for i in range(1, leng+1, step):
    if (i-1)%(leng//N)==0 and(i-1)%(leng//M)==0:
        if S[(i-1)//(leng//N)]!=T[(i-1)//(leng//M)]:
            print(-1)
            break
else:
    print(leng)

Submission status: Accepted

Solution code:
def gcd(x,y):
    while y>0:
        x,y = y,x%y
    return x
N,M = map(int,input().split())
S = input().strip()
T = input().strip()
a = gcd(N,M)
K = (N//a)*M
t = (N//a)*(M//a)
flag = 0
k = 0
while (k*t)//(K//N)<N and (k*t)//(K//M)<M:
    if S[(k*t)//(K//N)]!=T[(k*t)//(K//M)]:
        flag = 1
        break
    k += 1
if flag==0:
    print(K)
else:
    print(-1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from math import gcd
input = sys.stdin.readline
N, M = map(int, input().split())
S = list(input())[: -1]
T = list(input())[: -1]
g = gcd(N, M)
ln = N * M // g
x = 0
y = 0
while x < N and (y < M):
  if S[x] != T[y]:
    print(-1)
    exit(0)
  x += ln // M
  y += ln // N
print(ln)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
import numpy as np

N,M=map(int,input().split())
gcd=math.gcd(N,M)
lcm=N*M//gcd

S=input()
T=input()
i=1

L=np.array([lcm*i for i in range(1,max(N,M)) if lcm*i<=N*M])
S_list=L//M
T_list=L//N

if S[0]!=T[0]:
  print(-1)
else:
  for i in range(len(S_list)-1):
    if S[S_list[i]]!=T[T_list[i]]:
      print(-1)
      break
  else:
    print(lcm)

Submission status: Accepted

Solution code:
def examA():
    def gcd(x, y):
        if y == 0:
            return x
        while (y != 0):
            x, y = y, x % y
        return x

    def lcm(x, y):
        return x * y // gcd(x, y)
    N, M = LI()
    S = SI()
    T = SI()
    L = lcm(N,M)
    for i in range(N):
        if i*M%N!=0:
            continue
        cur = i*M//N
        #print(i,cur)
        if S[i]!=T[cur]:
            L = -1
            break
    print(L)
    return

def examB():
    class combination():
        # 素数のmod取るときのみ　速い
        def __init__(self, n, mod):
            self.n = n
            self.mod = mod
            self.fac = [1] * (n + 1)
            self.inv = [1] * (n + 1)
            for j in range(1, n + 1):
                self.fac[j] = self.fac[j - 1] * j % mod

            self.inv[n] = pow(self.fac[n], mod - 2, mod)
            for j in range(n - 1, -1, -1):
                self.inv[j] = self.inv[j + 1] * (j + 1) % mod

        def comb(self, n, r):
            if r > n or n < 0 or r < 0:
                return 0
            return self.fac[n] * self.inv[n - r] * self.inv[r] % self.mod
    N = I()
    A = LI()
    C = combination(N,mod)
    ans = 0
    cnt = 0
    for i in range(N):
        cnt += C.fac[N]*pow(i+1,mod-2,mod)
        cnt %= mod
        #print(cnt)
    #print(cnt)
    ans += cnt*A[0]
    for i in range(1,N):
        cnt = cnt + C.fac[N]*pow(i+1,mod-2,mod) - C.fac[N]*pow(N-i+1,mod-2,mod)
        cnt += mod
        cnt %= mod
        a = A[i]
        ans += cnt*a
        ans %= mod
        #print(cnt)
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examA()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Accepted

Solution code:
import fractions

n,m=list(map(int,input().split()))
s=input()
t=input()
l=n*m//fractions.gcd(n,m)

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

pos=0
while pos<l:
    if s[pos//m]!=t[pos//n]:
        print(-1)
        exit(0)

    pos+=p

print(l)

Submission status: Accepted

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

# from numba import njit
from math import gcd
# input = stdin.readline

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

# @njit
def solve(n,m,s,t):
  L = lcm(n,m)
  G = gcd(n,m)
  s_interval = L//n
  t_interval = L//m
  for i in range(G):
    if s[i*n//G] != t[i*m//G]:
      return -1
  return L
  

def main():
  N,M = map(int,input().split())
  s = input()
  t = input()
  print(solve(N,M,s,t))
  return

if __name__ == '__main__':
  main()

Submission status: Accepted

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

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

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

    print(L)

if __name__ == "__main__":
    main5()

Submission status: Accepted

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

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

    pair = dict()

    for i in range(1, N + 1):
        idx = (i - 1) * (L // N) + 1
        pair[idx] = S[i - 1]

    for i in range(1, M + 1):
        idx = (i - 1) * (L // M) + 1

        if idx in pair.keys():
            if pair[idx] != T[i - 1]:
                print(-1)
                exit()

    print(L)

if __name__ == "__main__":
    main4()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

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


def lcm(x, y):
    return (x * y) // math.gcd(x, y)
l = (lcm(n, m))

sdict = {}
s_num = []
for i, moji in enumerate(list(s)):
    num = i * l // n + 1
    sdict[num - 1] = moji
    s_num.append(num - 1)

tdct = {}
t_num = []
for i, moji in enumerate(list(t)):
    num = i * l // m + 1
    tdct[num - 1] = moji
    t_num.append(num - 1)

stlst = list(set(s_num) & set(t_num))

for i in stlst:
    if sdict[i] != tdct[i]:
        print(-1)
        exit()
print(l)

Submission status: Accepted

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

Submission status: Accepted

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


N, M = map(int, input().split())
S = input()
T = input()
x = gcd(N, M)
n = N // x
m = M // x

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

G=gcd(n,m)
a,b = n//G,m//G
s=s[0::a]
t=t[0::b]
if s==t: print(a*b*G)
else: print(-1)

Submission status: Accepted

Solution code:
from collections import defaultdict
from collections import deque
from collections import Counter
import itertools
import math

def readInt():
  return int(input())
def readInts():
  return list(map(int, input().split()))
def readChar():
  return input()
def readChars():
  return input().split()

n,m = readInts()
s = readChar()
t = readChar()

d = defaultdict(str)

l = n*m//math.gcd(n,m)
j = 0
for i in range(1,(n-1)*(l//n)+1+1,l//n):
  d[i]=s[j]
  j+=1
j = 0
for i in range(1,(m-1)*(l//m)+1+1,l//m):
  if not (d[i]=="" or d[i]==t[j]):
    #おつかれサンバ
    print(-1)
    exit()
  j+=1
print(l)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from math import gcd

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

    d = dict()
    l = (n * m) // gcd(n, m)
    ls = l // n
    lt = l // m

    for i in range(n):
        d[i*ls] = s[i]

    for i in range(m):
        if d.get(i*lt):
            if d[i*lt] != t[i]:
                return print(-1)

    print(l)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import gcd

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

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

Submission status: Accepted

Solution code:
import math

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

S=input()
T=input()

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

l=lcm(N,M)

if S[0] != T[0]:
    print(-1)
else:
    a=l//N
    b=l//M
    m=lcm(a,b)
    answer=0
    for n in range(m, l, m):
        c=n//a
        d=n//b
        if S[c]==T[d]:
            continue
        else:
            answer=1
            break
    if answer==0:
        print(l)
    else:
        print(-1)

Submission status: Accepted

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

from math import*
ans=N*M//gcd(N,M)

i=0
j=0
count_i=0
count_j=0
while i<N and j<M:
    if count_i==count_j:
        if S[i]!=T[j]:
            ans=-1
    if count_i>count_j:
        count_j+=ans//M
        j+=1
    elif count_j>count_i:
        count_i+=ans//N
        i+=1
    else:
        count_i+=ans//N
        count_j+=ans//M
        i+=1
        j+=1

print(ans)

Submission status: Accepted

Solution code:
import sys
N, M = list(map(int, input().split()))
S = input()
T = input()
if S[0] != T[0]:
    print(-1)
    sys.exit()
if N > M:
    N, M = M, N
    S, T = T, S


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


L = N * M // gcd(N, M)
n = L // N
m = L // M
l = n * m // gcd(n, m)
for i in range(l, L, l):
    if S[i // n] != T[i // m]:
        print(-1)
        sys.exit()
print(L)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
enum = enumerate
INF = 1001001001

def linput(ty=int, cvt=list):
	return cvt(map(ty,input().rstrip().split()))

def vinput(rep=1, ty=int, cvt=list):
	return cvt(ty(input().rstrip()) for _ in "*"*rep)

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

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

def main():
	N,M = linput()
	S,T = vinput(2,str)
	
	g = gcd(N,M)
	l = lcm(N,M)
	
	res = 0
	if S[::N//g]==T[::M//g]:
		#print(S[::N//g])
		#print(T[::M//g])
		res = l
	else:
		res = -1
	
	#sT = "No Yes".split()
	#print(sT[res])
	print(res)


if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def v(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
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
cnt = 0
ans = 0
inf = float("inf")

n,m = I()
s = v()
t = v()
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)
        sys.exit()

print(l)

Submission status: Accepted

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

# In[2]:


import math


# In[25]:


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


# In[26]:


g = math.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)


# In[ ]:

Submission status: Accepted

Solution code:
def resolve():
    '''
    code here
    '''
    import math
    N, M = [int(item) for item in input().split()]
    S = input()
    T = input()

    res = N * M // math.gcd(N,M)

    cycle_s = res // N
    cycle_t = res // M
    cycle_overlap = cycle_s * cycle_t // math.gcd(cycle_s, cycle_t)

    for i in range(res//cycle_overlap):        
        if T[i*cycle_overlap//cycle_t] == S[i*cycle_overlap//cycle_s]:
            pass
        else:
            res = -1
            break

    print(res)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

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

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

L=lcm(n,m)

isGood=True
cycle_s=L//n
cycle_t=L//m
cycle_lcm=lcm(cycle_s,cycle_t)
for i in range((L//cycle_lcm)):
    if s[cycle_lcm*i//cycle_s]!=t[cycle_lcm*i//cycle_t]:
        isGood=False
        break

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

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)
x = {}
for i in range(N):
    idx = i * (L // N)
    x[idx] = S[i]
for i in range(M):
    idx = i * (L // M)
    if idx in x and x[idx] != T[i]:
        print(-1)
        exit()
print(L)

Submission status: Accepted

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

'''if n<m:
    s,t=t,s
    snum,tnum=tnum,snum'''

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque, defaultdict
from math import sqrt, factorial, gcd
# def input(): return sys.stdin.readline()[:-1] # warning not \n
# def input(): return sys.stdin.buffer.readline().strip() # warning bytes
# def input(): return sys.stdin.buffer.readline().decode('utf-8')


def solve():
    n, m = [int(x) for x in input().split()]
    s = input()
    t = input()
    g = gcd(n, m)
    ans = n * m // g
    a, b = n // g, m // g
    x, y = 0, 0
    for i in range(g):
        if s[x] != t[y]:
            print(-1)
            return
        x += a
        y += b
    print(ans)
    
t = 1
# t = int(input())
for case in range(1,t+1):
    ans = solve()


"""

2 2 2 2 2

"""

Submission status: Accepted

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

cnt = math.gcd(N, M)
ans = N * M // cnt
a, b = 0, 0
flag = False
for i in range(cnt):
  if S[a] != T[b]:
    flag = True
    break
  a += N//cnt
  b += M//cnt
  
if flag:
  ans = -1
print(ans)

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

sn = L//M
tm = L//N

for i in range(N//sn):
    if S[i*sn] == T[i*tm]:
        continue
    else:
        print(-1)
        exit()
print(L)

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 x * y // gcd(x, y)


n_lcm = lcm(len(S), len(T))
gcd_nm = gcd(N, M)

s_step = N // gcd_nm
t_step = M // gcd_nm

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

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

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

def cond(candidate):
    count = gcd(n, m)
    n_step = n // count
    m_step = m // count

    for i in range(count):
        if s[n_step * i] != t[m_step * i]:
            return False
    return True

candidate = lcm(n, m)

if cond(candidate):
    print(candidate)
else:
    print(-1)

Submission status: Accepted

Solution code:
from math import gcd
n, m, S, T = open(0).read().split()
n, m = int(n), int(m)
l = n*m // gcd(n, m)

d = {}
t = l//n
for i in range(n):
    d[i*t] = S[i]
t = l//m
for i in range(m):
    if i*t not in d or d[i*t] == T[i]:
        d[i*t] = T[i]
    else:
        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()

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

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

print(L)

Submission status: Accepted

Solution code:
from math import gcd


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

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

l = lcm(n, m)
ln, lm = l // n, l // m
if all(s[i // ln] == t[i // lm] for i in range(0, l, lcm(ln, lm))):
    print(l)
else:
    print(-1)

Submission status: Accepted

Solution code:
from math import gcd


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

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

l = lcm(n,m)
ln, lm = l // n, l // m
for i in range(0, l, lcm(ln, lm)):
    if s[i // ln] != t[i // lm]:
        print(-1)
        break
else:
    print(l)

Submission status: Accepted

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

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


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

    N, M = il()
    S = iss()
    T = iss()
    G = math.gcd(N, M)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,m = map(int,ipt().split())
    s = input()
    t = input()
    g = math.gcd(n,m)
    l = n*m//g
    sg = n//g
    tg = m//g
    for i in range(g):
        if s[sg*i] != t[tg*i]:
            print(-1)
            exit()

    print(l)

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math
read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N, M = map(int, readline().split())
    S = readline().rstrip().decode('utf-8')
    T = readline().rstrip().decode('utf-8')

    G = math.gcd(N, M)

    A = ''.join(S[::N // G])
    B = ''.join(T[::M // G])

    if A == B:
        answer = N * M // G
    else:
        answer = -1
    print(answer)


if __name__ == '__main__':
    main()

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

L=lcm(N,M)

i=0
j=0
while 0<=i<N and 0<=j<M:
    nowi=i*(L//N)
    nowj=j*(L//M)
    #print(i,j,nowi,nowj)
    if nowj==nowi:
        if S[i]!=T[j]:

            print(-1)
            exit()

    if nowi>nowj:
        j+=1
    elif nowi<nowj:
        i+=1
    else:
        i+=1
        j+=1
print(L)

Submission status: Accepted

Solution code:
from math import gcd
from collections import defaultdict

N, M = map(int, input().split())
S = input()
T = input()
g = N//gcd(N, M)*M
ans = defaultdict(bool)
for i in range(N):
    ans[i*g//N] = S[i]
ok = True
for i in range(M):
    idx = i*g//M
    if ans[idx] and ans[idx] != T[i]:
        ok = False
        break
if ok:
    print(g)
else:
    print(-1)

Submission status: Accepted

Solution code:
import bisect,copy,heapq,string
from collections import *
from math import *
from itertools import *
import sys
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n, m = MAP()
s = input()
t = input()
k = gcd(n,m)
l = n*m//k

for i in range(0,l,l//k):
        if (n*i) % l == (m*i) % l == 0 and s[n*i//l] != t[m*i//l]:
                print(-1)
                exit()
print(l)

Submission status: Accepted

Solution code:
from math import gcd
from collections import defaultdict

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

ans = n*m // gcd(n,m)
d = defaultdict(lambda : '?')

for i,si in enumerate(s):
    d[i * ans//n] = si

for j,tj in enumerate(t):
    if(not d[j * ans//m] in ['?', tj]):
        print(-1)
        exit()

print(ans)