Problem:


Score : 300 points

Problem Statement

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

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

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

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

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

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

Constraints

1 \leq N,M \leq 10^5

S and T consist of lowercase English letters.

|S|=N

|T|=M

Input

Input is given from Standard Input in the following format:

N M
S
T

Output

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

Sample Input 1

3 2
acp
ae

Sample Output 1

6

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

Sample Input 2

6 3
abcdef
abc

Sample Output 2

-1

Sample Input 3

15 9
dnsusrayukuaiia
dujrunuma

Sample Output 3

45



Sample input:
3 2
acp
ae


Sample output:
6

Submission status: Accepted

Solution code:
import sys

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

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

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

print(L)

Submission status: Accepted

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

if S[0] != T[0]:ans = -1

elif N % M != 0 and M % N != 0:
    if N >= M:
        while True:
            if N * a % M == 0:
                ans = N * a
                b = int(N*a/M)
                for i in range(int(N/b)):
                    if T[a*i] != S[b*i]:
                        ans = -1
                        break
                break
            else:
                a += 1
    elif N < M:
        while True:
            if M * a % N == 0:
                ans = M * a
                b = int(M*a/N)
                for i in range(int(M/b)):
                    if T[b*i] != S[a*i]:
                        ans = -1
                        break
                break
            else:
                a += 1

elif N % M == 0:
    b = int(N/M)
    ans = N
    for i in range(M):
        if T[i] != S[b*i]:
            ans = -1
            break   

elif M % N == 0:
    b = int(M/N)
    ans = M
    for i in range(N):
        if S[i] != T[b*i]:
            ans = -1
            break   

print(ans)

Submission status: Accepted

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

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

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

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

print(m)

Submission status: Accepted

Solution code:
import numpy as np# your code goes here
def eucrid(a, b):
	if (a > b):
		buf = a
		a = b
		b = buf
	if (b % a == 0):
		return a
	else:
		return eucrid(b%a, a)
		
def main():
	buf = input().split()
	s = input()
	t = input()
	n = len(s)
	m = len(t)
	
	big = n*m//eucrid(n, m)
	flag = big
	"""
	for i in range(big):
		if (i%(big//n) == 0 and i%(big//m) == 0):
			#print(i, n, m)
			#print((i+1)//(big//n), (i+1)//(big//m))
			if(s[(i+1)//(big//n)] != t[(i+1)//(big//m)]):
				flag = -1
	"""			
	for i in range(n):
		if((i*(big//n))%(big//m) == 0):
			if(s[i] != t[(i*(big//n))//(big//m)]):
				flag = -1

	print(flag)
	#print(s, t, n, m)
	
	
main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import fractions
n,m = map(int,input().split())
s=input()
t=input()
def answer(n,m,s,t):
    if s[0] != t[0]:
        return -1
    g = fractions.gcd(n,m)
    l = n*m//g
    i = 1
    while l*i < m*n:
        if s[l*i//m] != t[l*i//n]:
            return -1
        else:
            i += 1
    return l
print(answer(n,m,s,t))

Submission status: Accepted

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

def agc(n,m,s,t):
    if s[0]!=t[0]:
        return -1
    g=fractions.gcd(n,m)
    if g==1:
        return  n*m
    l=n*m//g
    i=1
    while l*i<m*n:
        if s[int(l*i//m)]!=t[int(l*i//n)]:
            return -1
        i+=1
    return  int(l)
print(agc(n,m,s,t))

Submission status: Accepted

Solution code:
# time complexity: O(lg(max{a, b}))
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)


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


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

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

for i in range(N):
    if i % n == 0:
        S_idx = i
        T_idx = m * i // n
        if S[S_idx] != T[T_idx]:
            print(-1)
            exit(0)

for i in range(M):
    if i % m == 0:
        S_idx = n * i // m
        T_idx = i
        if S[S_idx] != T[T_idx]:
            print(-1)
            exit(0)
else:
    print(L)

Submission status: Accepted

Solution code:
def gcd(a,b):
  while b>0:
    a,b=b,a%b
  return a
 
x,y=map(int,input().split())
S=input()
T=input()
GCD=gcd(x,y)
LCM=(x * y) // GCD
 
x_new=x//GCD
y_new=y//GCD
for i in range(0,GCD):
  if S[(x_new)*i]==T[(y_new)*i]:
    result=LCM
  else:
    result=-1
    break
print(result)

Submission status: Accepted

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

def gcd(n, m):
    if n < m:
        return gcd(m, n)
    if m == 0:
        return n
    else:
        return gcd(m, n % m)

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

print(ans)

Submission status: Accepted

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

x,y=map(int,input().split())
S=input()
T=input()
GCD=gcd(x,y)
LCM=(x * y) // GCD

x_new=x//GCD
y_new=y//GCD
for i in range(0,GCD):
  if S[(x_new)*i]==T[(y_new)*i]:
    result=LCM
  else:
    result=-1
    break
print(result)

Submission status: Accepted

Solution code:
class MathAlgo(object):

    @classmethod
    def gcd(cls, a, b):
        if b == 0:
            return a
        else:
            return cls.gcd(b, a%b)


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

base = MathAlgo.gcd(N,M)

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

Submission status: Accepted

Solution code:
import fractions


def two_abbreviation(n, m, s, t):
    common = int(fractions.gcd(n, m) + 10 ** -6)
    s_common = [a for i, a in enumerate(zip(s)) if i % int(n / common + 10 ** -6) == 0]
    t_common = [a for i, a in enumerate(zip(t)) if i % int(m / common + 10 ** -6) == 0]
    ret = int(n * m / common + 10 ** -6) if s_common == t_common else -1
    return ret


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

print(str(two_abbreviation(N, M, S, T)))

Submission status: Accepted

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


def gcd(x, y):
    if x < y:
        return gcd(y, x)
    elif y == 0:
        return x
    else:
        return gcd(y, x % y)


g = gcd(N, M)
if (g == 1 and S[0] == T[0]) or S[::N // g] == T[::M // g]:
    print(N * M // g)
else:
    print(-1)

Submission status: Accepted

Solution code:
def gcd(a,b): return a if b==0 else gcd(b,a%b)
def lcm(a,b): return a*b//gcd(a,b)
n,m=map(int,input().split())
s=input()
t=input()
l=lcm(n,m)
d={}
f=l
for i in range(max(n,m)):
    o=i*(l//n)
    p=i*(l//m)
    if i<n and o not in d:
        d[o]=s[i]
    elif i<n and o in d and d[o]!=s[i]:
        f=-1
    if i<m and p not in d:
        d[p]=t[i]
    elif i<m and p in d and d[p]!=t[i]:
        f=-1
print(f)

Submission status: Accepted

Solution code:
from fractions import gcd # python 3.4
# from math import gcd # from python 3.5 
def lcm(a,b):
    return int(a*b/gcd(a,b))

N,M = map(int, input().split())
S = input()
T = input()
L= lcm(N,M)
ans = dict()
for i in range(N):
    idx = i*(L//N)
    ans[idx] = S[i]

for j in range(M):
    idx = j*(L//M)
    if idx in ans.keys():
        if ans[idx]==T[j]:
            continue
        else:
            print(-1)
            break
else:
    print(L)

Submission status: Accepted

Solution code:
import sys


def next_str() -> str:
    result = ""
    while True:
        tmp = sys.stdin.read(1)
        if tmp.strip() != "":
            result += tmp
        elif tmp != '\r':
            break
    return result


def next_int() -> int:
    return int(next_str())


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


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


def main() -> None:
    n, m = [next_int() for _ in range(2)]
    s, t = [next_str() for _ in range(2)]
    l = lcm(n, m)
    dic = dict()

    for i, c in enumerate(s):
        j = i * l // n
        dic[j] = c

    for i, c in enumerate(t):
        j = i * l // m
        if j in dic and dic[j] != c:
            print(-1)
            return

    print(l)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def inpl(): return [int(i) for i in input().split()]
def gcd(a,b):
    if b == 0:
        return a
    return gcd(b,a%b)

N, M = inpl()
gcdnm = gcd(N, M)
S = input()
T = input()
S = ''.join([S[i*(N//gcdnm)] for i in range(gcdnm)])
T = ''.join([T[i*(M//gcdnm)] for i in range(gcdnm)])
if S == T:
    print(N*M//gcdnm)
else:
    print(-1)

Submission status: Accepted

Solution code:
from fractions import gcd
# https://img.atcoder.jp/agc028/editorial.pdf
N, M = map(int,input().split())
S = input()
T = input()

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

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

print(L)

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
s = input()
t = input()
def gcd(a, b):
    while b > 0:
        a, b = b, a%b
    return a
g = gcd(n, m)
l = n * m // g
for i in range(0, g):
  if s[i * n//g] != t[i * m//g]:
    print('-1')
    exit()
print(l)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import fractions
n, m = map(int,input().split())
s = list(map(str,input()))
t = list(map(str,input()))
k = 0
q = fractions.gcd(n, m)
l = n * m // q #lcm(n, m)
p = int(l/n * l/m / fractions.gcd(l/n, l/m)) #lcm(l/n, l/m)
for i in range(0, int(l/p)):
  if s[i * p//(l//n)] != t[i * p//(l//m)]:
    print('-1')
    exit()
print(l)

Submission status: Accepted

Solution code:
import fractions
n, m = map(int,input().split())
s = list(map(str,input()))
t = list(map(str,input()))
k = 0
q = fractions.gcd(n, m)
l = n * m // q #lcm(n, m)
p = int(l/n * l/m / fractions.gcd(l/n, l/m)) #lcm(l/n, l/m)
for i in range(0, int(l/p)):
  if s[i * p//(l//n)] != t[i * p//(l//m)]:
    print('-1')
    break
  else:
    k = k + 1

if k == l/p:
  print(l)

Submission status: Accepted

Solution code:
import fractions
n, m = map(int,input().split())
s = list(map(str,input()))
t = list(map(str,input()))
k = 0
q = fractions.gcd(n, m)
l = n * m // q #lcm(n, m)
p = int(l/n * l/m / fractions.gcd(l/n, l/m)) #lcm(l/n, l/m)
for i in range(0, int(l/p)):
  if s[0] != t[0]:
    print('-1')
    break
  elif q == 1:
    print(l)
    break
  elif s[i * p//(l//n)] != t[i * p//(l//m)]:
    print('-1')
    break
  else:
    k = k + 1

if k == l/p:
  print(l)

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)

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

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

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
S=input()
T=input()
list_S=list(S)
list_T=list(T)
Number_i=[i for i in range(N)]
Number_iMN=[]
for i in Number_i:
  Number_iMN.append(i*M/N)
Number_j=[j for j in range(M)]
Kaburi_j=list(set(Number_iMN)&set(Number_j))
Kaburi_i=[]
for j in Kaburi_j:
  Kaburi_i.append(int(j*N/M))
counter=0
Flag=0
Kaburi_Size=len(Kaburi_i)
while counter<=Kaburi_Size-1:
  if list_S[int(Kaburi_i[counter])]==list_T[int(Kaburi_j[counter])]:
    pass
  else:
    Flag=1
    break
  counter+=1
def gcd(a,b):
  while b>0:
    a,b=b,a%b
  return a
if Flag==1:
  print(-1)
else:
  print(int(N*M/gcd(N,M)))

Submission status: Accepted

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


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

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

main()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,m = LI()
    s = S()
    t = S()
    l = n * m // fractions.gcd(n,m)
    si = ti = 0
    sc = l // n
    tc = l // m
    while si < l and ti < l:
        if si == ti:
            if s[si//sc] != t[ti//tc]:
                return -1
            si += sc
            ti += tc
        elif si < ti:
            si += sc
        else:
            ti += tc

    return l


print(main())

Submission status: Accepted

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

for i in range(g):
    if s[i * n // g] != t[i * m // g]:
        flag = False

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

Submission status: Accepted

Solution code:
import sys
def euclid(data):
    a=data[0]
    for b in data[1:]:
        if(b<a):
            a,b=b,a
        while(1):
            r=b%a
            if(r==0):
                break
            else:
                b=a
                a=r
    return a


S_l,T_l=map(int,input().split())
S=input()
T=input()

lcm=S_l*T_l//euclid([S_l,T_l])
dS=lcm//S_l
dT=lcm//T_l

llcm=dS*dT//euclid([dS,dT])
ddS=llcm//dS
ddT=llcm//dT

i=0
while(ddS*i < S_l and ddT*i < T_l):
    if(S[ddS*i]!=T[ddT*i]):
        print(-1)
        sys.exit(0)
    i+=1
print(lcm)

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)

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

Submission status: Accepted

Solution code:
import math

 

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


def lcd(n,m):
    return int(n * m / gcd(n,m))
def gcd(n,m):
    if n % m == 0:
        return m
    else:
        return gcd(m,n % m)
#    return int(m*n/math.gcd(n,m))
    
def prove(n,m):
    n_i = int(lcd(n,m)/n)
    m_i = int(lcd(n,m)/m)
    n_list=[S[m_i*i] for i in range(gcd(n,m))]
    m_list=[T[n_i*i] for i in range(gcd(n,m))]
#    print(c)
#    print(pair[m])
    if n_list==m_list:
        return lcd(n,m)
    else:
        return -1


print(prove(N,M))

Submission status: Accepted

Solution code:
import math

 

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


def lcd(n,m):
    return int(n * m / gcd(n,m))
def gcd(n,m):
    if n % m == 0:
        return m
    else:
        return gcd(m,n % m)
#    return int(m*n/math.gcd(n,m))
    
def prove(n,m):
    n_i = int(n/gcd(n,m))
    m_i = int(m/gcd(n,m))
    n_list,m_list=[],[]
    for i in range(gcd(n,m)):
        n_list += S[i*n_i]
        m_list += T[i*m_i]
#    print(c)
#    print(pair[m])
    if n_list==m_list:
        return lcd(n,m)
    else:
        return -1


print(prove(N,M))

Submission status: Accepted

Solution code:
import math

 

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

pair = {N:S,M:T}


def lcd(n,m):
    return int(n * m / gcd(n,m))
def gcd(n,m):
    if n % m == 0:
        return m
    else:
        return gcd(m,n % m)
#    return int(m*n/math.gcd(n,m))
    
def prove(n,m):
    if gcd(n,m)==1:
        return lcd(n,m)
    global pair
    n_i = int(n/gcd(n,m))
    m_i = int(m/gcd(n,m))
    n_list = pair[n][::n_i]
    m_list = pair[m][::m_i]
#    print(c)
#    print(pair[m])
    if n_list[0:len(m_list)]==m_list:
        return lcd(n,m)
    else:
        return -1
n = max(pair.keys())
m = min(pair.keys())
if pair[N][0]!=pair[M][0]:
    print(-1)
elif N==M:
    if S==T:
        print(N)
    else:
        print(-1)
else:
    print(prove(n,m))

Submission status: Accepted

Solution code:
from fractions import gcd

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

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

lenS,lenT = len(S),len(T)
L = lcm(N,M)
isok = True
for i in range(L):
    if i*(L//M)>=len(S) or i*(L//N)>=len(T):
        break
    elif S[i*(L//M)]!=T[i*(L//N)]:
        isok = False
        break
        
if isok:
    print(L)
else:
    print("-1")

Submission status: Accepted

Solution code:
def gcd(x, y):
  if y == 0:
    return x
  return gcd(y, x % y)
N, M = map(int, input().split())
S = input()
T = input()
g = gcd(N, M)
ans = int(N * M / g)
for i in range(g):
  if S[int(N / g * i)] != T[int(M / g * i)]:
    ans = -1
    break
print(ans)

Submission status: Accepted

Solution code:
def gcd(m, n):
    r = m % n
    return gcd(n, r) if r else n

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

Submission status: Accepted

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

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

lcm=int(n*m/g)

s1=int(lcm/n)
s2=int(lcm/m)

#print(s1, s2, int(n/s2))

f=1
for i in range(int(n/s2)):
    #print(s2*i, s[s2*i], s1*i, t[s1*i])
    if s[s2*i] != t[s1*i]:
        f=0

if f:
    print(lcm)
else:
    print("-1")

Submission status: Accepted

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

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

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

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

poss = True
for j in range(m):
    idx = j * L / m
    if idx in a:
        poss &= a[idx] == t[j]

if poss:
    print L
else:
    print -1

Submission status: Accepted

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

def get_lcm(a, b, gcd=0):
    if gcd == 0:
        return a * b // get_gcd(a, b)
    else:
        return a * b // gcd


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

S = input()
T = input()

gcd = get_gcd(N, M)
lcm = get_lcm(N, M, gcd)

if [s for i, s in enumerate(S) if i % (lcm / M) == 0] == [t for i, t in enumerate(T) if i % (lcm / N) == 0]:
    print(lcm)
else:
    print(-1)

Submission status: Accepted

Solution code:
n,m = (int(i) for i in input().split())
s = input()
t = input()
def gcd(a,b):
	if a%b: return gcd(b,a%b)
	else: return b
g = gcd(n,m)
ng, mg = n//g, m//g
if all(s[i*ng] == t[i*mg] for i in range(g)) :
    print(n*m//g)
else :
    print(-1)

Submission status: Accepted

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

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

l = n * m // gcd(n, m)
a = l // n
b = l // m
#print(a, b)
#a(i-1) = b(j-i) -> ai = bj + (a-b)
res = False
clear_all = True
for i in range(1,n+1):
    if (a*i - (a-b)) % b == 0:
        j = (a * i - (a-b)) // b
        if not s[i-1] == t[j-1]:
            clear_all = False
if clear_all:
    res = True
if res:
    print(l)
else:
    print(-1)

Submission status: Accepted

Solution code:
import sys

def gcd(a,b):
    if a<b:
        a,b = b,a
    if a%b==0:
        return b
    else:
        return gcd(a%b,b)
        
N,M=map(int,input().split())
length=N*M//gcd(N,M)

S=input()
T=input()

a=length//N
b=length//M
l=a*b//gcd(a,b)
s=l//a
t=l//b

for i in range(gcd(N,M)):
    if S[i*s]!=T[i*t]:
        print(-1)
        sys.exit()
print(length)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding:utf-8

import sys


input = sys.stdin.readline
INF = float('inf')


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


# 整数(x, y)最大公約数を求める
def gcd(x, y):
    if x % y == 0:
        return y
    else:
        x, y = y, x % y
        return gcd(x, y)


# 整数(x, y)最小公倍数を求める
def lcm(x, y):
    return x * y // gcd(x, y)


def solve(N, M, S, T):
    L = lcm(N, M)
    ln, lm = L // N, L // M

    # 文字列Xのk * lcm(L/N, L/M) (k = 0 ~ gcd(N, M) - 1)番目の文字は
    # S[k * lcm(L/N, L/M) / (L/N)]と
    # T[k * lcm(L/N, L/M) / (L/M)]で使われる
    D = lcm(ln, lm)
    A = D // ln
    B = D // lm
    for i in range(gcd(N, M)):
        if S[A * i] != T[B * i]:
            break
    else:
        return L
    return -1


N, M = inpl()
S = input()
T = input()
print(solve(N, M, S, T))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding:utf-8

import sys


input = sys.stdin.readline
INF = float('inf')


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


# 整数(x, y)最大公約数を求める
def gcd(x, y):
    if x % y == 0:
        return y
    else:
        x, y = y, x % y
        return gcd(x, y)


# 整数(x, y)最小公倍数を求める
def lcm(x, y):
    return x * y // gcd(x, y)


def solve(N, M, S, T):
    L = lcm(N, M)
    ln, lm = L // N, L // M

    # 文字列Xのk * D + 1(k = 0 ~ L // D)番目の文字は
    # Sのk * D // ln + 1(k = 0 ~ D // lm)文字目と、
    # Tのk * D // lm + 1(k = 0 ~ D // ln)文字目の
    # 両方で使われる
    D = lcm(ln, lm)

    li_S = []
    for i in range(0, N, D // ln):
        li_S.append(S[i])

    li_T = []
    for i in range(0, M, D // lm):
        li_T.append(T[i])

    # print(li_S, li_T)
    # S, Tの両方で使われる文字が一致しているか判定
    if li_S == li_T:
        return L
    else:
        return -1


N, M = inpl()
S = input()
T = input()
print(solve(N, M, S, T))

Submission status: Accepted

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

def gcd(a, b):
    if a < b:
        a, b = b, a

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


def main():
    N, M = [int(a) for a in input().split()]

    S = input()
    T = input()
    L = N * M // gcd(N, M)
    a1 = L // N
    a2 = L // M
    cc = a1 * a2 // gcd(a1, a2)
    for i in range(0, L, cc):
        if S[i // a1] != T[i // a2]:
            print(-1)
            return
    print(L)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

Submission status: Accepted

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

s = list(input())
t = list(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)

#x = ['' for _ in range(l)]
step = l // n
step_m = l // m
for i in range(n):
    if (step * i) % step_m == 0:
        if s[i] != t[(step * i) // step_m]:
            #print(step, i, (step * i) // step_m, s[i], t[(step * i) // step_m])
            print(-1)
            exit()

print(l)

Submission status: Accepted

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

g = gcd(N, M)
l = int(N * M / g)

for i in range(g):
    if S[int(N/g*i)] != T[int(M/g*i)]:
        l = -1
        break

print(l)

Submission status: Accepted

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

Submission status: Accepted

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


def lcm(x: int, y: int):
    '''
    See:
    https://note.nkmk.me/python-gcd-lcm/
    '''
    from fractions import gcd
    return (x * y) // gcd(x, y)


def main():
    n, m = map(int, input().split())
    s = input()
    t = input()
    size = lcm(n, m)
    part_s = [s[i] for i in range(0, n, size // m)]
    part_t = [t[j] for j in range(0, m, size // n)]

    for si, ti in zip(part_s, part_t):
        if si != ti:
            print(-1)
            exit()

    print(size)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
s = str(input())
t = str(input())
def get_gcd(a, b): #最大公約数を求める関数
    if a < b:
        a, b = b, a
    if a % b == 0:
        return b
    else:
        return get_gcd(b, a % b)
def get_lcm(a, b, gcd): #みたまんまそういうやつです
    lcm = a * b // gcd
    return lcm
lcm = get_lcm(n,m,get_gcd(n,m)) #lcmはn,m最小公倍数
lcm2 = get_lcm(lcm/n,lcm/m,get_gcd(lcm/n,lcm/m)) #lcm２はlcm/nとlcm/mの最小公倍数
ans = 0
for i in range(int(lcm//lcm2)):
    if s[int(i*lcm2//(lcm/n))] == t[int(i*lcm2//(lcm/m))]:
        pass
    else:
        ans = 1
        break
if ans == 1:
    print(-1)
else:
    print(lcm)

Submission status: Accepted

Solution code:

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

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

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

cs = {}

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

result = L

for i in range(M):
    j = L // M * i + 1
    if j in cs and cs[j] != T[i]:
        result = -1
        break

print(result)

Submission status: Accepted

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


def lcm(x: int, y: int):
    '''
    See:
    https://note.nkmk.me/python-gcd-lcm/
    '''
    from fractions import gcd
    return (x * y) // gcd(x, y)


def main():
    n, m = map(int, input().split())
    s = input()
    t = input()
    size = lcm(n, m)
    dn = size // n
    dm = size // m
    part_s = list()
    part_t = list()

    for i in range(0, n, dm):
        part_s.append(s[i])

    for i in range(0, m, dn):
        part_t.append(t[i])

    for si, ti in zip(part_s, part_t):
        if si != ti:
            print(-1)
            exit()

    print(size)


if __name__ == '__main__':
    main()

Submission status: Accepted

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


def lcm(x: int, y: int):
    '''
    See:
    https://note.nkmk.me/python-gcd-lcm/
    '''
    from fractions import gcd
    return (x * y) // gcd(x, y)


def main():
    n, m = map(int, input().split())
    s = input()
    t = input()
    size = lcm(n, m)
    dn = size // n
    dm = size // m
    part_s = [s[0]]
    part_t = [t[0]]
    i = dm
    j = dn

    while i < n:
        part_s.append(s[i])
        i += dm

    while j < m:
        part_t.append(t[j])
        j += dn

    for si, ti in zip(part_s, part_t):
        if si != ti:
            print(-1)
            exit()

    print(size)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M =  map(int, input().split(' '))
def gcd(a, b):
    a, b = (a, b) if a >= b else (b, a)
    while b > 0:
        a, b = b, a % b
    return a

S = input()
T = input()
g = gcd(N, M)
#print('gcd',g)
#print('',N//g,M//g)
#print(S[0::N//g] ,T[0::M//g])
if S[0::N//g] == T[0::M//g]:
    print(N*M//g)
else:
    print(-1)

Submission status: Accepted

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

def gcd(m,n):
    x = max(m,n)
    y = min(m,n)
    if x % y == 0:
        return y
    else:
        return gcd(y,x%y)

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

d = gcd(N,M)
l = lcm(N,M)

s = [0 for i in range(0,d)]
t = [0 for i in range(0,d)]

a = int(l/M)
b = int(l/N)

for i in range(0,d):
    s[i] = S[i*a]
    t[i] = T[i*b]

if s == t:
    print(l)
else:
    print(-1)

Submission status: Accepted

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

Submission status: Accepted

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

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

if listS[0] != listT[0]:
    print(-1)
else:
    checkI = a*b // fractions.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:
# -*- coding: utf-8 -*-
"""
Created on Sun Oct 14 08:52:34 2018
AGC028A
@author: maezawa
"""

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

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

lcm = n*m//gcm(n,m)
possible = True

for k in range(n):
    if k*m%n == 0:
        if k*m//n < m and s[k] != t[k*m//n]:
            possible = False
            #print(k, k*n//m, s[k], t[k*n//m])
            break
for k in range(m):
    if k*n%m == 0:
        if k*n//m < n and t[k] != s[k*n//m]:
            possible = False
            #print(k, k*m//n, t[k], s[k*m//n])
            break
                                
    
if possible:
    print(lcm)
else:
    print(-1)