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:
def Euclidean(a, b):
    if a<b:
        a, b = b, a
    while True:
        m = a%b
        if m==0 or b==1:
            return b
        a = b
        b = m

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

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

gcm = Euclidean(N, M)
gcd = int(N*M/gcm)
#print(gcm, gcd)

if N<M:
    N, M = M, N
    S, T = T, S
#print(N, M)
#print(S, T)

a = int(gcd/M)
b = int(gcd/N)
ab = a*b
for i in range(int(gcd/ab)):
    #print(i*a, i*b)
    if S[i*a]!=T[i*b]:
        print(-1)
        exit()
print(gcd)

Submission status: Accepted

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

import sys
import itertools
import math

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

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

    if N < M:
        t = M
        M = N
        N = t
        q = S
        S = T
        T = q

    d = gcd(N,M)
    c = N * M // d

    ret = -1
    slen = c
    nstep = slen // N
    mstep = slen // M

    dd = gcd(nstep, mstep)
    cc = nstep * mstep // dd

    good = True
    for k in range(0, slen, cc):
        u = (k // nstep) % N
        j = (k // mstep) % M
        if S[u] != T[j]:
            good = False
            break
    if good:
        ret = slen

    # 出力
    print("{}".format(ret))


if __name__ == '__main__':
    main()

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

def lcm(a, b):
	return int(a * b // gcd (a, b))
answer =lcm(N,M)

G =gcd(N,M)

for k in range(G):
    if S[int(k*N/G)] !=  T[int(k*M/G)]:
        answer =-1

print(answer)

Submission status: Accepted

Solution code:
a = input().split()
N = int(a[0])
M = int(a[1])
S = list(input())
T = list(input())

if N > M:
    pre = N
    lat = M
else:
    pre = M
    lat = N

while True:
    if pre % lat == 0:
        GCD = int(lat)
        break
    else:
        stp = lat
        lat = pre % lat
        pre = stp

LCM = int(N * M / GCD)

N_l = int(N / GCD)
M_l = int(M / GCD)

ch=0
for i in range(GCD):
    if S[i*N_l] != T[i*M_l]:
        ch = 1
        break

if ch == 0:
    print(LCM)
else:
    print(-1)

Submission status: Accepted

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

L = lcm(n,m)
ss = L/n
ts = L/m
seen = {}
works = True

ind = 0
for char in s:
    if ind in seen:
        if not seen[ind] == char:
            works = False
            break
    else:
        seen[ind] = char
    ind += ss

ind = 0
for char in t:
    if ind in seen:
        if not seen[ind] == char:
            works = False
            break
    else:
        seen[ind] = char
    ind += ts

if works: print L
else: print -1

Submission status: Accepted

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

import math
import fractions


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


if __name__ == '__main__':
    N, M = map(int, input().split(' '))
    S = input()
    T = input()

    L = lcm(N, M)

    S_index_X = [int(i * L / N) for i in range(N)]
    T_index_X = [int(i * L / M) for i in range(M)]

    common_index = set(S_index_X).intersection(set(T_index_X))
    for i in common_index:
        si = int(i * N / L)
        ti = int(i * M / L)
        if S[si] != T[ti]:
            print(-1)
            exit(0)
    print(L)

Submission status: Accepted

Solution code:
def Gcd(a, b):#ユークリッド互除法
	return Gcd(b, a % b) if b else a

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

#最小公倍数
p = (N * M) // Gcd(N, M)
re = p

for i in range(0,p,max((p//N),(p//M))):
	#交差点
	if i % (p//N) == 0 and i % (p//M) == 0:
		#異なる文字
		if S[i // (p//N)] != T[i // (p//M)]:
			re = -1
			break
print(re)

Submission status: Accepted

Solution code:
qqq,qqq2 = list(map(int,input().split()))

x = input()
y = input()

if len(x) < len(y):
	x, y = y, x

lx = len(x)
ly = len(y)
lxy = lx * ly
r = lx % ly
while r != 0:
	lx = ly
	ly = r
	r = lx % ly

lcm = int(lxy / ly)
ret = lcm

lx = len(x)
ly = len(y)
stepX = int(lcm / lx)
stepY = int(lcm / ly)

dic = {}
i = 0
for s in x:
	dic[i] = s
	i = i + stepX

i = 0
for s in y:
	if i in dic:
		if dic[i] != s:
			ret = -1
			break
	i = i + stepY

print(ret)

Submission status: Accepted

Solution code:
import fractions

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

gcd = fractions.gcd(N,M)
if N >= M:
    high = N
    high_s = S
    high_r = N//gcd
    low = M
    low_s = T
    low_r = M//gcd
else:
    high = M
    high_s = T
    high_r = M//gcd
    low = N
    low_s = S
    low_r = N//gcd

cnt = low // low_r
ans = high * low_r
for i in range(0,cnt):
    high_c = high_s[ i * high_r ]
    low_c = low_s[ i * low_r ]
    if high_c != low_c:
        ans = -1
print(ans)

Submission status: Accepted

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

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

def cmp(x, y, l):
	if len(x) < len(y):
		x, y = y, x
	lx = int(l/len(x))
	ly = int(l/len(y))
	lc = lcm(lx,ly)
	lt = [i*lc for i in range(int(l/lc))]
	for i in lt:
		if i%lc == 0 and x[int(i/lx)] != y[int(i/ly)]:
			return False
	return True

def cmp2(x, y, l):
	if len(x) < len(y):
		x, y = y, x
	lx = int(l/len(x))
	ly = int(l/len(y))
	for i in range(l):
		if i%lx == 0 and i%ly == 0 and x[int(i/lx)] != y[int(i/ly)]:
			return False
	return True


if __name__ == '__main__':
	N, M = list(map(int, input().split()))
	S = input()
	T = input()
	L = lcm(N,M)
	if not cmp(S,T,L):
		print(-1)
	else:
		print(L)

Submission status: Accepted

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

def Euclid(a,b):
    m = max(a,b)
    n = min(a,b)
    if m == n:
        return m
    else:
        return Euclid(n, m-n)

N, M = [int(x) for x in stdin.readline().rstrip().split()]
S = stdin.readline().rstrip()
T = stdin.readline().rstrip()
euc = Euclid(N,M)

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


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


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


@mt
def slv(N, M, S, T):
    if N < M:
        S, T = T, S
        N, M = M, N

    if gcd(N, M) == 1:
        if S[0] != T[0]:
            return -1
        return N * M

    else:
        c = gcd(N, M)
        ans = lcm(N, M)
        for i in range(0, ans, ans//c):
            j = i // (M//c)
            k = i // (N//c)
            error_print(i, j, k)
            if S[j] != T[k]:
                return -1
        return lcm(N, M)


def main():
    N, M = read_int_n()
    S = read_str()
    T = read_str()
    print(slv(N, M, S, T))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#coding:utf-8
import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
n,m = map(int,input().split())
s=input()
t=input()
lcm = lcm(n,m)
a = int(lcm/n)
b = int(lcm/m)
for i in range(fractions.gcd(n,m)):
    if s[i*b]==t[i*a]:
        pass
    else:
        print (-1)
        exit()
print (lcm)

Submission status: Accepted

Solution code:
import math

n,m = map(int, input().split())
s = input()
t = input()
g = 1
div = []
for i in range(2,min(n,m)+1):
    if min(n,m)%i == 0:
        div.append(i)
for i in div:
    if max(n,m)%i == 0:
        g = i
G = g*(n/g)*(m/g)

ans = int(G)
i = 0
while (G/m)*i <= n-1:
    if s[int((G/m)*i)] == t[int((G/n)*i)]:
        pass
    else:
        ans = -1
        break
    i += 1
print(ans)

Submission status: Accepted

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


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


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

if listS[0]!=listT[0]:
    print(-1)
else:
    checkI = a*b // gcd(a, b)
    if checkI > l:
        print(l)
    else:
        index=0
        flag=0
        while index < l//min(a, b):
            if index*checkI//a > len(listS)-1 or index*checkI//b > len(listT)-1:
                break
            elif listS[index*checkI//a] != listT[index*checkI//b]:
                print(-1)
                flag=1
                break
            else:
                index+=1
        if flag==0:
            print(l)

Submission status: Accepted

Solution code:


def gcd(a,b):
    """Compute the greatest common divisor of a and b"""
    while b > 0:
        a, b = b, a % b
    return a

def lcm(a, b):
    """Compute the lowest common multiple of a and b"""
    return a * b / gcd(a, b)


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

    L=int(lcm(N,M))

    N_ = int(L/N)
    M_ = int(L/M)

    L_ = int(lcm(N_,M_))

    for i in range(0,L,L_):
        if(S[int(i/N_)] != T[int(i/M_)]):
            print(-1)
            return 0;

    print(L)
    return 0;

main()

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

nagasa=lcm(N, M)

aidaS=nagasa//N
aidaT=nagasa//M
#print(aidaS,aidaT)

aidaOnajiCheck=lcm(aidaS, aidaT)

jyoken=True

#print(nagasa//aidaOnajiCheck)

for i in range((nagasa//aidaOnajiCheck)):
  #print((aidaOnajiCheck//aidaS)*i)
  if(not (S[(aidaOnajiCheck//aidaS)*i]==T[(aidaOnajiCheck//aidaT)*i])):
    jyoken=False

if(jyoken):
  print(nagasa)
else:
  print(-1)

Submission status: Accepted

Solution code:
N,M = map(int,input().split(" "))
S = input()
T = input()
# gcd
def gcd (a,b):
    if a < b:
        a,b = b,a
    return a if b == 0 else gcd(b,a%b)


g = gcd(N,M)
l = N*(M//g)
dic = {}
for i in range(N):
    dic[i*(l//N)] = S[i]
for i in range(M):
    if (i*(l//M)) in dic:
        if dic[i*(l//M)] != T[i]:
            print(-1)
            exit(0)

print(l)

Submission status: Accepted

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

def main():
    N, M = map(int, input().split())
    S = input()
    T = input()
    result = N * M / gcd(N, M)
    cand = (result / N) * (result / M) / gcd(int((result / N)), int((result / M)))
    for i in range(0, int(result / cand)):
        if S[int((i * cand) / (result / N))] != T[int((i * cand) / (result / M))]:
            return '-1'
    return int(result)
print(main())

Submission status: Accepted

Solution code:
N,M = list(map(int,input().split()))
S = input()
T = input()
sl = list(S)
tl = list(T)
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
def lcm(x, y):
    return int((x * y) / gcd(x, y))

lcm = lcm(N,M)
Sd = int(lcm/N)
St = int(lcm/M)
kaisu = min(int((N-1)/St),int((M-1)/Sd))
flag = 0
for i in range(kaisu+1):
    if sl[St*i] != tl[Sd*i]:
        flag = 1
if flag == 0:
    print(lcm)
else:
    print(-1)

Submission status: Accepted

Solution code:
def LCM(a, b):
    tmp = a * b
    while b != 0:
        a, b = b, a % b
    return tmp // a

N, M = map(int, input().split())
s = input()
t = input()
n = LCM(N, M)
a = n // N
b = n // M
for i in range(min((N - 1) // b, (M - 1) // a) + 1):
    if s[b * i] != t[a * i]:
        print("-1")
        break

else:
    print(n)

Submission status: Accepted

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

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

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


ans = int(lcm(N, M))

# L / len(x)
L_N = int(ans / N)
# M / len(x)
N_M = int(ans / M)

S_list = []
for i in range(1, ans+1, L_N):
    S_list.append(i)

T_list = []
for i in range(1, ans+1, N_M):
    T_list.append(i)

intersect = set(T_list) & set(S_list)

S_in = [x for x, y in enumerate(S_list) if y in intersect]
T_in = [x for x, y in enumerate(T_list) if y in intersect]

flg = True
for x, y in zip(S_in, T_in):
    if S[x] == T[y]:
        continue
    else:
        flg = False

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

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split(" ")))
s = input()
t = input()
def gcd(a,b):
  while b > 0:
    a, b = b, a % b
  return a
d = gcd(n, m)
l = n*m // d
res = l

s_sep = n//d
t_sep = m//d

for si,ti in zip(s[::s_sep], t[::t_sep]):
  if si!=ti:
    res = -1
    break
print(res)

Submission status: Accepted

Solution code:

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

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

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

gcdNM = gcd(N, M)
lcmNM = lcm(N, M)

isGood = True
for i in range(gcdNM):
    if S[i * N // (gcdNM)] != T[i * M // (gcdNM)]:
        isGood = False
        break

if isGood and T[0] == S[0]:
    print(lcmNM)
else:
    print(-1)

Submission status: Accepted

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

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

sl, tl = map(int, input().split())
s = input()
t = input()

m = lcm(sl,tl)

mps = m // sl
mpt = m // tl

tmp = 0
width = max(mps,mpt)
ans = True

while tmp < m:
    if tmp % mps == 0 and tmp % mpt == 0:
        if s[tmp//mps] != t[tmp//mpt]:
            ans = False
            break
    tmp += width

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

Submission status: Accepted

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

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

    key = lcm(N, M)
    n = key // N
    m = key // M
    n_list = []
    for i in range(0, key, n):
        n_list.append(i)
    m_list = []
    for j in range(0, key, m):
        m_list.append(j)

    #print(n_list, m_list)
    i = 0
    j = 0
    while True:
        if i >= len(n_list) or j >= len(m_list):
            break
        if i >= len(S) or j >= len(T):
            break
        if n_list[i] == m_list[j]:
            if S[i] != T[j]:
                print(-1)
                return 0
        if n_list[i] > m_list[j]:
            j += 1
        elif n_list[i] < m_list[j]:
            i += 1
        else:
            i += 1
            j += 1
    print(key)

AGC028A()

Submission status: Accepted

Solution code:
[m,n] = list(map(int, input().split()))
s = input()
t = input()
ans = -1

for i in range(m):
	if m%(i+1) == 0 and n%(i+1) ==0:
		gcd = i+1

m1 = m//gcd
n1 = n//gcd

flag = 1
for i in range(gcd):
	if s[i*m1]!=t[i*n1]:
		flag = 0
	
	
if flag == 1:
	ans = m*n//gcd

print(ans)

Submission status: Accepted

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

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

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

l = lcm(N, M)
s = S[0:N:l//M]
t = T[0:M:l//N]

if all(map(lambda a: a[0] == a[1], zip(s, t))):
    print(l)
else:
    print(-1)

Submission status: Accepted

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

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

if S[0]!=T[0]:
    print(-1)
else:
    if N==M:
        print(int(N*M)) if S==T else print(-1)
    else:
        g = gcd(N, M)
        if g==1:
            print(int(N*M))
        else:
            flag = False
            s, t = N//g, M//g
            ss = list(map(lambda x: int(x*s), list(range(0,g))))
            tt = list(map(lambda x: int(x*t), list(range(0,g))))
            for i,j in zip(ss,tt):
                if S[i]!=T[j]:
                    flag = True
            if flag:
                print(-1)
            else:
                print(int(s*t*g))

Submission status: Accepted

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

n,m = map(int,input().split())
nl = list(input())
ml = list(input())
lcm = n * m // gcd(n,m)
if gcd(n,m) == 1:
    if nl[0] == ml[0]:
        print(lcm)
    else:
        print(-1)
else:
    if nl[::n//gcd(n,m)] == ml[::m//gcd(n,m)]:
        print(lcm)
    else:
        print(-1)

Submission status: Accepted

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

n,m = map(int,input().split())
a = gcd(n,m)
b = (n*m)//a


s = input()
t = input()
ans = b

for i in range(a):
    if s[i*b//m] != t[i*b//n]:
        ans = -1
print(ans)

Submission status: Accepted

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

if N>=M:
	x=N
	y=M
else:
	x=M
	y=N
while y!=0:
	a=y
	y=x%y
	x=a
G=x


L = (N*M)//G
cycle = L//G

flag=0

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

Submission status: Accepted

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


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


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: Accepted

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

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

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

a = lcm//n
b = lcm//m

flag=0
le = min(n,m)//(min(n,m)//gcd_)

for i in range(le):
    if s[i*b]!=t[i*a]:
        flag=1

if flag==1:
    print(-1)
else:
    print(lcm)

Submission status: Accepted

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

n,m=map(int,input().split())
s=input()
t=input()
cnt=1
i=0
flag=0

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

r=l/m

while cnt<n:
  if s[int(i*l/m)]==t[int(i*l/n)]:
    flag=1
    cnt+=r
    i+=1
  else:
    flag=0
    break

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

Submission status: Accepted

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

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

re = -1
if S == T:
    re = N
elif S[0] == T[0]:
    min_num = (N * M)  // gcd(N, M) # 最小公倍数を求める（基本はこれが答え）
    re = min_num
    # 重なる部分が同じ文字かを調べる
    s_d = min_num // N
    t_d = min_num // M
    # 最小公倍数みる
    st_min = (s_d * t_d) // gcd(s_d, t_d)
    st = st_min
    i = 1
    while st // s_d < N and st // t_d < M:
        if S[st // s_d] != T[st // t_d]:
            re = -1
            break
        else:
            i += 1
            st = st_min * i

print(re)

Submission status: Accepted

Solution code:
from fractions import gcd

N, M = tuple(int(i) for i in input().split())
S = input()
T = input()

lcm = N * M // gcd(N, M)
min_s = min((N, M))
S_ = S[::lcm//M]
T_ = T[::lcm//N]

if S_ == T_:
    print(lcm)
else:
    print(-1)

Submission status: Accepted

Solution code:
from fractions import gcd

n, m = [int(i) for i in input().split()]
S = input()
T = input()

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

SA = set()
SB = set()

for i in range(0, g, g//n):
    SA.add(i)

for i in range(0, g, g//m):
    SB.add(i)

SC = SA & SB

for s in SC:
    if S[s//(g//n)] != T[s//(g//m)]:
        print(-1)
        exit()

print(g)

Submission status: Accepted

Solution code:
def GCD(a, b):
	if b > a:
		tmp = a
		a = b
		b = tmp
	if a % b == 0:
		return b
	return GCD(b, a % b)

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

def judge():
	N, M = map(int, raw_input().split())
	S = raw_input()
	T =raw_input()
	L = LCM(N, M)
	S_pos = [0] * N
	T_pos = [0] * M
	for i in range(N):
		S_pos[i] = i * L/N
	for i in range(M):
		T_pos[i] = i * L/M
	i = 0
	j = 0
	while i < N and j < M:
		if S_pos[i] == T_pos[j]:
			if S[i] != T[j]:
				return -1
			i += 1
			j += 1
		elif S_pos[i] < T_pos[j]:
			i += 1
		else:
			j += 1
	return L

print judge()

Submission status: Accepted

Solution code:
def gcb(A, B):
    while B != 0:
        A, B = B, A%B
    return A

N, M = map(int, input().split())
S = input()
T = input()
can = True
agc = N // gcb(N, M) * M
L_N = agc // N
L_M = agc // M
i = 0
while i*L_M < N and i*L_N < M:
    if S[i*L_M] != T[i*L_N]:
        can = False
        break
    i += 1

if can:
    print(agc)
else:
    print(-1)

Submission status: Accepted

Solution code:
import fractions
a = list(map(int,input().split()))

b = list(input())

c = list(input())

d = fractions.gcd(a[0],a[1])
d = (a[0] * a[1])//d

l = d //a[0]
ll = d//a[1]
lll = (l*ll)//fractions.gcd(l,ll)
p = 0
for i in range(1,d+1,lll):
    if i == 1:
        if b[0] != c[0]:
            p = 1
            break
    else:
        if b[(i-1) //l] != c[(i-1) // ll]:
            p = 1
            break


if p == 0:
    if d != max(a):
        print(d)
    else:
        print(-1)
else:
    print(-1)

Submission status: Accepted

Solution code:
# from math import gcd
from fractions import gcd

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


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

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

i = 0

while True:
  i += 1
  L = i*lcm(N, M)
  N_list = [(L//N)*k + 1 for k in range(N)]
  M_list = [(L//M)*k + 1 for k in range(M)]

  # print(N_list)
  # print(M_list)

  memo = {}

  for idx, n in enumerate(N_list):
    memo[n] = S[idx]

  for idx, m in enumerate(M_list):
    if m in memo.keys():
      if memo[m] != T[idx]:
        break
  else:
    print(L)
    exit(0)

  # if L == N*M:
  break

print(-1)

Submission status: Accepted

Solution code:
import fractions

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

S=list(input())
T=list(input())

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

NM=lcm(N,M)

#array=[0]*NM

battingS=[]
battingT=[]
#Scount=0
for i in range(0,N,NM//M):
  battingS.append(S[i])
  #Scount+=1
  #print(array)

Tcount=0

for j in range(0,M,NM//N):
  battingT.append(T[j])
  #Scount+=1
  '''
  if array[j]!=0 and array[j]!=T[Tcount]:
    print(-1)
    exit()
  else:
    array[j]=T[Tcount]
    Tcount+=1
  #print(array)
  '''

for i in range(len(battingS)):
  if battingS[i]!=battingT[i]:
    print(-1)
    exit()
#print(battingS,battingT)
print(NM)

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)

a = l // n
b = l // m

for i in range(0, l, a*b):
    if s[i // a] != t[i // b]:
        print(-1)
        break
else:
    print(l)

Submission status: Accepted

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

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

div = gcd(n,m)
length = div * (n//div) * (m//div)

difs = length // n
dift = length // m


g = gcd(difs,dift)
gd = g * (difs//g) * (dift//g)
moves = gd//difs
movet = gd//dift

check = True
i = 0
k = 0

while i < n and k < m and check:
    if s[i] != t[k]:
        check = False
    i += moves
    k += movet
if check:
    print(length)
else:
    print('-1')

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from fractions import gcd
from bisect import bisect_left
def inpl(): return list(map(int, input().split()))
N, M = inpl()

S = input()
T = input()

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

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

a = G//N
b = G//M

X = [a*i for i in range(N)]
Y = [b*j for j in range(M)]

for i, x in enumerate(X):
    j = bisect_left(Y, x)
    if j < M and Y[j] == x:
        if S[i] != T[j]:
            print(-1)
            break
else:
    print(G)

Submission status: Accepted

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

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)
D = lcm(L // M, L // N)

for i in range(0, L, D):
    if S[i // (L // N)] != T[i // (L // M)]:
        print("-1")
        exit()
else:
    print(L)

Submission status: Accepted

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

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

gcd = gcd(n, m)
L = int(n * m / gcd)

a = int(L/n)
b = int(L/m)

flag=True

if n > m:
    for j in range(n):
        i = j * a
        if (int(i%a) == 0 and int(i%b) == 0):
            if not S[int(i/a)] == T[int(i/b)]:
                flag = False
else:
    for j in range(m):
        i = j * b
        if (int(i%a) == 0 and int(i%b) == 0):
            if not S[int(i/a)] == T[int(i/b)]:
                flag = False
                
if flag:
    print(L)
else:
    print("-1")

Submission status: Accepted

Solution code:
from sys import stdin
il = lambda func=int: list(map(func, stdin.readline().rstrip().split()))
ils = lambda n, s="int(input())": [eval(s) for _ in range(n)]
def gcd(a, b):
    if a < b: return gcd(b, a)
    if b == 0: return a
    return gcd(b, a%b)
def lcm(a, b):
    return a * b // gcd(a, b)

n, m = il()
s = input()
t = input()
aa = gcd(n, m)
bb = lcm(n, m)
cc = aa // bb
for i in range(aa):
    if s[n//aa*i] != t[m//aa*i]:
        print(-1)
        exit()
print(bb)

Submission status: Accepted

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

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

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

lcm = lcmCalc(n, m)

# str1 = ""
# for i in range(lcm):
# 	str1 += "-"

flg = 0
for i in range(n):
	index = i * lcm // n + 1
	if (index - 1) % (lcm // m) == 0:
		j = (index - 1) // (lcm // m)
		if s[i] != t[j]:
			print("-1")
			flg = 1
			break
if flg == 0:
	print(lcm)


# 	str1 = str1[:index] + s[i] + str1[index+1:]

# flg = 0
# for i in range(m):
# 	index = i * lcm // m + 1
# 	if str1[index:index+1] != "-" and str1[index:index+1] != t[i]:
# 		print("-1")
# 		flg = 1
# 		break

# if flg == 0:
# 	print(lcm)

Submission status: Accepted

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

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

s = input()
t = input()

a = kouyaku(n, m)

sn = n // a
sm = m // a

ok = True
for i in range(a):
    if(s[i*sn] != t[i*sm]):
        print(str(-1))
        ok = False
        break

if ok == True:
    print(sn*sm*a)

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()
T = input()
L = (n*m) // gcd(n, m)
c = 0

xs = L//n
xt = L//m
step = xs * xt

for i in range(0, L, step):
    if S[i//xs] != T[i//xt]:
        print(-1)
        exit()
print(L)

Submission status: Accepted

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)

for i in range(n):
    if i*m%n==0:
        j = i*m//n
        if s[i]!=t[j]:
            print(-1)
            exit()
print(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: Accepted

Solution code:
import fractions


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

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

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

Submission status: Accepted

Solution code:
import math


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

if N>M:
    N,M = M,N
    S,T = T,S
    
def gcd(a, b):
    while b:
	    a, b = b, a % b
    return a
    
L = int(M*N/gcd(N, M))

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

print(L)

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

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

g = lcm(n,m)

if n < m:
    sm = n
    bi = m
    ls = s
    bs = t
else:
    sm = m
    bi = n
    ls = t
    bs = s
a = g//sm
b = g//bi
flg = False
for i in range(sm):
    p = i * a
    if p % b == 0:
        if bs[p//b] != ls[i]:
            flg = True
            break
if flg:
    print(-1)
else:
    print(g)

Submission status: Accepted

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

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



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


    length = lcm(n,m)
    stepn = length//n
    stepm = length//m
    step_lcm = lcm(stepn,stepm)

    if s[0] != t[0]:
        print(-1)
        return 0
    else:
        if step_lcm >= length:
            print(length)
            return 0
        else:
            steps = step_lcm//stepn
            stept = step_lcm//stepm

            pos_s = 0
            pos_t = 0
            i = 0
            pos_s = 0
            pos_t = 0
            while pos_s < n and pos_t < m:
                if not s[pos_s] == t[pos_t]:
                    print(-1)
                    return 0
                i+=1
                pos_s = i*steps
                pos_t = i*stept
            print(length)

mas()