Problem:


Score : 300 points

Problem Statement

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

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

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

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

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

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

Constraints

1 \leq N,M \leq 10^5

S and T consist of lowercase English letters.

|S|=N

|T|=M

Input

Input is given from Standard Input in the following format:

N M
S
T

Output

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

Sample Input 1

3 2
acp
ae

Sample Output 1

6

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

Sample Input 2

6 3
abcdef
abc

Sample Output 2

-1

Sample Input 3

15 9
dnsusrayukuaiia
dujrunuma

Sample Output 3

45



Sample input:
3 2
acp
ae


Sample output:
6

Submission status: Time Limit Exceeded

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

snum=[i*g/n+1 for i in range(n)]
tnum=[i*g/m+1 for i in range(m)]
#print(snum,tnum)

if n<m:
    s,t=t,s
    snum,tnum=tnum,snum
for i in range(len(snum)):
    if snum[i] in tnum:
        if s[i]!=t[tnum.index(snum[i])]:
            print(-1)
            exit()
print(g)

Submission status: Time Limit Exceeded

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

print(L)

Submission status: Time Limit Exceeded

Solution code:
from math import gcd

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

L = N*M // gcd(N, M)
X = ["0" for _ in range(L)]

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

print(L)

Submission status: Time Limit Exceeded

Solution code:
from math import gcd


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

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

Submission status: Time Limit Exceeded

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()
l = n*m//gcd(n, m)

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

Submission status: Time Limit Exceeded

Solution code:
import fractions
import sys
input=sys.stdin.readline
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()
k=lcm(n,m)
ans=[""for i in range(k)]
ans[0]=s[0]
for i in range(1,n):
    ans[i*(k//n)]=s[i]
for i in range(1,m):
    if not ans[i*(k//m)]:
        ans[i*(k//m)]=t[i]
    else:
        if ans[i*(k//m)]!=t[i]:
            print(-1)
            exit()
print(k)

Submission status: Time Limit Exceeded

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()
k=lcm(n,m)
ans=[""for i in range(k)]
ans[0]=s[0]
for i in range(1,n):
    ans[i*(k//n)]=s[i]
for i in range(1,m):
    if not ans[i*(k//m)]:
        ans[i*(k//m)]=t[i]
    else:
        if ans[i*(k//m)]!=t[i]:
            print(-1)
            exit()
print(k)

Submission status: Time Limit Exceeded

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)
box = ["" for _ in range(L)]
for i in range(N):
    box[i * (L // N)] = S[i]
for j in range(M):
    temp = j * (L // M)
    if box[temp] == "":
        box[temp] = T[j]
    elif box[temp] == T[j]:
        continue
    else:
        print(-1)
        break
else:
    print(L)

Submission status: Time Limit Exceeded

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

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

lcm = N * M // math.gcd(N, M)
#1,(L/N) +1, 2*(L/N) +1..(N-1)*(L/N)+1
tekito =[]
for i in range(1,N):
  tekito.append(i*(lcm//N)+1)
  
for i in range(1,M):
  k = i*(lcm//M)+1
  if k in tekito:
#    print(k)
#    print(tekito.index(k)+1)
#    print(i)
    if S[tekito.index(k)+1] != T[i]:
      print(-1)
      exit()
print(lcm)

Submission status: Time Limit Exceeded

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

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

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


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

z = ['' for i in range(f2)]
for i in range(n):
    z[i*x] = s[i]
for i in range(m):
    if z[i*y] != '' and z[i*y] != t[i]:
        print(-1)
        sys.exit()
print(f2)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def f(a,b):
    if b:
        return f(b,a%b)
    return a
n,m=map(int,input().split())
s=list(input())
t=list(input())
a=n//f(n,m)*m
p=['' for i in range(a)]
n,m=a//n,a//m
p[::n]=s
p[::m]=t
print(a if p[::n]==s and p[::m]==t else -1)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

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

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

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

  


print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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


dic = {i+1: [] for i in range(int((N*M) / gcd(N,M)))}
L = len(dic)
ans = L

for n in range(N):
  k = int(n*(L/N))+1
  #print(k)
  dic[k].append(S[n])

#print(dic)
for m in range(M):
  k = int(m * (L/M) + 1)
  if len(dic[k]) == 0:continue
  else: 
    #print(T[m],dic[k])
    if dic[k][0] != T[m]:
      ans = -1
      break


print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True


# ワーシャルフロイド (任意の2頂点の対に対して最短経路を求める)
# 計算量n^3 (nは頂点の数)
def warshall_floyd(d, n):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d


# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

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

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定



# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret


# ここから書き始める
n, m = map(int, input().split())
s = input()
t = input()
l = lcm(n, m)
# print("l =", l)
x = ["" for i in range(l)]
cnt1 = 0
while cnt1 < n:
    x[l // n * cnt1] = s[cnt1]
    cnt1 += 1
# print("x =", x)
cnt2 = 0
ans = l
while cnt2 < m:
    if x[l // m * cnt2] not in ["", t[cnt2]]:
       ans = -1
       break
    cnt2 += 1
print(ans)

Submission status: Time Limit Exceeded

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

G = N * M // fractions.gcd(N, M)
slist = [i*(G//N) for i in range(N)]
mlist = [i*(G//M) for i in range(M)]
sm = set(slist) & set(mlist)
for i in sm:
    si = slist.index(i)
    mi = mlist.index(i)
    if S[si] != T[mi]:
        print(-1)
        exit()

print(G)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

a = lcm(n,m)
l = [0 for i in range(a)]
l1 = [0 for i in range(a)]
for i in range(n):
  l[int(i*(a/n))+1-1] = s[i]
for j in range(m):
  l1[int(j*(a/m))+1-1] = t[j]
for j,k in zip(l,l1):
  if j!=k and j!=0 and k!=0:
    print("-1")
    exit()
else:
  print(a)

Submission status: Time Limit Exceeded

Solution code:
import fractions

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

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

    lcmn = lcm(N, M)
    l = ['' for i in range(lcmn+1)]
    for i in range(0, N):
        l[(lcmn//N)*i+1] = S[i]

    for i in range(0, M):
        if l[(lcmn//M)*i+1] != '' and l[(lcmn//M)*i+1] != T[i]:
            return -1

    return lcmn

print(main())

Submission status: Time Limit Exceeded

Solution code:
import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
def myAnswer(N:int,M:int,S:str,T:str) -> int:
   L = lcm(N,M)
   setS = [1]
   for n in range(1,N):
      setS.append(n * L//N + 1)
   setT = [1]
   for m in range(1,M):
      setT.append(m * L//M + 1)
   # print(setS,setT,L)
   for n,i in enumerate(setS):
      if(i in setT):
         if(S[n] != T[setT.index(i)]):
            return -1
      # for m,j in enumerate(setT):
      #    if(i == j and S[n] != T[m]):
      #       # print(i,j,S[n],T[m],n,m)
      #       return -1
   else:
      return L

def modelAnswer():
   return
def main():
   N,M = map(int,input().split())
   S = input()
   T = input()
   print(myAnswer(N,M,S,T))
if __name__ == '__main__':
   main()

Submission status: Time Limit Exceeded

Solution code:
import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
def myAnswer(N:int,M:int,S:str,T:str) -> int:
   L = lcm(N,M)
   setS = [1]
   for n in range(1,N):
      setS.append(n * L//N + 1)
   setT = [1]
   for m in range(1,M):
      setT.append(m * L//M + 1)
   # print(setS,setT,L)
   for n,i in enumerate(setS):
      for m,j in enumerate(setT):
         if(i == j and S[n] != T[m]):
            # print(i,j,S[n],T[m],n,m)
            return -1
   else:
      return L

def modelAnswer():
   return
def main():
   N,M = map(int,input().split())
   S = input()
   T = input()
   print(myAnswer(N,M,S,T))
if __name__ == '__main__':
   main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions

import copy

# import heapq
# from collections import deque
# import decimal

sys.setrecursionlimit(10000001)
INF = sys.maxsize
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


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

    def multiple(a, b):
        return a * b // euclid(a, b)

    n, m = ns()
    s = list(input())
    t = list(input())

    gcd = multiple(n, m)

    s_idx = [gcd // n * i for i in range(n)]
    t_idx = [gcd // m * i for i in range(m)]

    ans = ["@" for _ in range(gcd+2)]
    for i, si in enumerate(s_idx):
        ans[si] = s[i]
    for i, ti in enumerate(t_idx):
        if ans[ti] != "@" and ans[ti] != t[i]:
            print(-1)
            exit(0)
    print(gcd)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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


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

s1=input()

s2=input()

len_moji = lcm(n,m)

len_s1 = []

len_s2 = []

for i in range(n):
    len_s1.append(i*len_moji//n+1)

for i in range(m):
    len_s2.append(i*len_moji//m+1)
#print(len_s1)
#print(len_s2)
count = 0
for ix, vs1 in enumerate(len_s1):
    for jx in range(count,len(len_s2)):
        #print(vs1, len_s2[jx])
        if vs1 < len_s2[jx]:
            break
        if vs1 == len_s2[jx]:
            count = jx
            if s1[ix] != s2[jx]:
                print(-1)
                exit()
            break
print(len_moji)

Submission status: Time Limit Exceeded

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


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

s1=input()

s2=input()

len_moji = lcm(n,m)

len_s1 = []

len_s2 = []

for i in range(n):
    len_s1.append(i*len_moji//n+1)

for i in range(m):
    len_s2.append(i*len_moji//m+1)
#print(len_s1,len_s2)

for ix, vs1 in enumerate(len_s1):
    for jx, vs2 in enumerate(len_s2):
        if vs1 == vs2:
            if s1[ix] != s2[jx]:
                print(-1)
                exit()
print(len_moji)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
N,M=map(int,input().split())
S=input()
T=input()
L=N*M//gcd(N,M)
ans=L


U=[]
V=[]

#1個目
for i in range(N):
  U.append( [i*(L//N),S[i]])
#2個目
for i in range(M):
  V.append( [i*(L//M),T[i]])
#print(U)
#print(V)

for i in U:
  for j in V:
    #print(i,j)
    if i[0]==j[0] and i[1]!=j[1]:
      print(-1)
      exit()


#  U[i*(L//N)]=S[i]
#  if U[j*(L//M)]!="#" and U[j*(L//M)]!=T[j]:
print(ans)

Submission status: Time Limit Exceeded

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

L=N*M//gcd(N,M)
#print(L)
U=["#" for _ in range(L)]
ans=L

for i in range(N):
  U[i*(L//N)]=S[i]
#print(U)

for j in range(M):
  if U[j*(L//M)]!="#" and U[j*(L//M)]!=T[j]:
    ans=-1
    break
  else:
    U[j*(L//M)]=T[j]

#print(U)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

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

ans = lcm

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

Submission status: Time Limit Exceeded

Solution code:
# たぶん最小の値は最小公倍数になりそう

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


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


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


l = lcm(n, m)
arr = [0 for _ in range(l)]

for i in range(n):
    x = i * (l // n)
    arr[x] = s[i]

for i in range(m):
    x = i * (l // m)
    if arr[x] != 0 and arr[x] != t[i]:
        print(-1)
        exit()
print(l)

Submission status: Time Limit Exceeded

Solution code:
def main():
    from fractions import gcd
    import sys

    n, m = map(int, input().split())
    s, t = input(), input()
    l = n * m // gcd(n, m)
    a = [l // n * i + 1 for i in range(n)]
    b = [l // m * i + 1 for i in range(m)]
    c = set(a) & set(b)
    for x in list(c):
        i = a.index(x)
        j = b.index(x)

        if s[i] != t[j]:
            print(-1)
            exit()
    else:
        print(l)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import fractions


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

def check():
    N, M = map(int, input().split())
    S = input()
    T = input()
    length = lcm(N,M)
        
    for i in range(length):
        if i%(length//N)==0 and i%(length//M)==0:
            if S[i//(length//N)] != T[i//(length//M)]:
                return -1
    return length
  
print(check())

Submission status: Time Limit Exceeded

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

from fractions import gcd
def lcm(a):
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

long=lcm([n,m])

ln=int(long/n)
lm=int(long/m)

ans=[]
ok=True
for i in range(long):
    an=i%ln
    am=i%lm
    kn=i//ln
    km=i//lm
    if (an==0)&(am==0):
        if s[kn]==t[km]:
            ans.append(s[kn])
        else:ok=False
    elif an==0:
        ans.append(s[kn])
    elif am==0:
        ans.append(t[km])
    else:
        ans.append("a")
lll=len(ans)
if not ok:
    lll=-1

print(lll)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd


def main():
    s_length, t_length = map(int, input().split())
    s = input()
    t = input()
    lcm = s_length * t_length // gcd(s_length, t_length)
    check = ["" for _ in range(lcm)]
    base = lcm // s_length
    for i in range(s_length):
        check[base * i] = s[i]
    base = lcm // t_length
    for i in range(t_length):
        if (0 < i and (check[base * i] != "" and check[base * i] != t[i])) or (i == 0 and t[0] != check[0]):
            print(-1)
            break
    else:
        print(lcm)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
import sys
n, m = map(int, input().split())
s = input()
t = input()
if s[0]==t[0]:
    g = gcd(n, m)
    x = g*(n//g)*(m//g)
    num_s, num_t = x//n, x//m
    for i in range(x):
        if (i-1)%num_s==0 and (i-1)%num_t==0:
            if s[(i-1)//num_s] == t[(i-1)//num_t]:
                continue
            else:
                print(-1)
                sys.exit()
    print(x)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
import sys
n, m = map(int, input().split())
s = input()
t = input()
if s[0]==t[0]:
    result = ""
    g = gcd(n, m)
    x = g*(n//g)*(m//g)
    num_s, num_t = x//n, x//m
    for i in range(x):
        if (i-1)%num_s==0 and (i-1)%num_t==0:
            if s[(i-1)//num_s] == t[(i-1)//num_t]:
                result = result+s[(i-1)//num_s]
            else:
                print(-1)
                sys.exit()
        elif (i-1)%num_s==0:
            result = result+s[(i-1)//num_s]
        elif (i-1)%num_t==0:
            result = result+t[(i-1)//num_t]
        else:
            result = result+"a"
    print(x)
else:
    print(-1)

Submission status: Time Limit Exceeded

Solution code:
# gcdより長いのは存在しなさそう（勘）なので存在するとしたらgcd
# 実際に試していく
n, m = map(int, input().split())
s, t = input(), input()


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


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


u = gcd(n, m)
v = [None for _ in range(u)]
x1 = 0
while x1 < n:
    p = x1 * (u // n) + 1
    # print("p = {}".format(p))
    # if v[p - 1] == None:
    #     v[p - 1] = s[x1]
    # else:
    #     print("すでに入ってるのでおしまい")
    v[p - 1] = s[x1]
    x1 += 1
x2 = 0
while x2 < m:
    p = x2 * (u // m) + 1
    if v[p - 1] == None:
        if x2 > 0:
            v[p - 1] = t[x2]
        else:
            if s[0] == t[0]:
                continue
            else:
                print(-1)
                exit()
    else:
        if v[p - 1] != t[x2]:
            print(-1)
            exit()
    x2 += 1
print(u)

Submission status: Time Limit Exceeded

Solution code:
import fractions

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

temp = n*m//fractions.gcd(n,m)
s_step = temp//n
t_step = temp//m

s_index = [1+s_step*i for i in range(n)]
t_index = [1+t_step*i for i in range(m)]

index = set(s_index)&set(t_index)

ans = temp

if len(index):
  for i in index:
    if t[t_index.index(i)] != s[s_index.index(i)]:
      ans = -1
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

s_num = [0] * n
t_num = [0] * m
s_num[0], t_num[0] = 1, 1
l = n * m / gcd(n, m)

for i in range(1, n):
    s_num[i] = i * l / n + 1

for i in range(1, m):
    t_num[i] = i * l / m + 1

match_num = list(set(s_num) & set(t_num))
ans = l

for i in range(len(match_num)):
    s_str = s[s_num.index(match_num[i])]
    t_str = t[t_num.index(match_num[i])]

    if s_str != t_str:
        print('-1')
        exit()

print(int(ans))

Submission status: Time Limit Exceeded

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

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

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

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

l = lcm(n, m)

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

print(l)

Submission status: Time Limit Exceeded

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

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

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

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

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

x[0] = s[0]
for i in range(1, n):
    x[(l//n) * i] = s[i]

for i in range(1, m):
    if x[(l//m) * i] == t[i]:
        continue
    if x[(l//m) * i] != " ":
        print(-1)
        exit()
        # sys.exit(0)

print(l)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

S = input()
T = input()

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

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

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

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

print(L)

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
def lcm(a,b):
    return(a*b//gcd(a,b))

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

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

Submission status: Time Limit Exceeded

Solution code:
import fractions

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

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

s_idx = [i * l//n + 1 for i in range(n)]
t_idx = [i * l//m + 1 for i in range(m)]

dup_idx = set(s_idx) & set(t_idx)

for d in dup_idx:
    si = s_idx.index(d)
    ti = t_idx.index(d)
    if s[si] != t[ti]:
        print(-1)
        break
else:
    print(l)

Submission status: Time Limit Exceeded

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

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

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

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

x = set(a) & set(b)

for i in x:
    if s[a.index(i)] != t[b.index(i)]:
        print(-1)
        exit()

print(l)

Submission status: Time Limit Exceeded

Solution code:
import fractions

N,M=map(int,input().split())
d=N*M//fractions.gcd(N,M)
a=d//N
b=d//M

S=input()
dS={}
for i in range(N):
    dS[a*i]=S[i]

T=input()
dT={}
for i in range(M):
    dT[b*i]=T[i]

f=True
for i in range(d):
    if i in dS and i in dT and dS[i]!=dT[i]:
        f=False
        break

print(d if f else -1)

Submission status: Time Limit Exceeded

Solution code:
import sys

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)
X = [0 for i in range(L)]

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys

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)
X = ["A" for i in range(L)]

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

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

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
n,m=map(int,input().split())
s=input()
t=input()
p=gcd(n,m)
ans=n*m//p
tt=[0 for _ in range(ans)]
for i in range(n):
	tt[i*(ans//n)]=ord(s[i])
for i in range(m):
	if tt[i*(ans//m)]!=ord(t[i]) and tt[i*(ans//m)]!=0:
		print(-1)
		exit()
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import fractions
N, M = map(int, input().split())
S = input()
T = input()
lcm = (N*M) // fractions.gcd(N, M)
if S[0] != T[0]:
    print(-1)
elif N == M and S != T:
    print(-1)
else:
    tmp = lcm // N
    tmp2 = lcm // M
    tmp_s = [tmp*i for i in range(N)]

    for i in range(M):
        if tmp2*i in tmp_s:
            if T[i] != S[tmp2*i // tmp]:
                print(-1)
                exit(0)
    print(lcm)

Submission status: Time Limit Exceeded

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

def lcm(N, M):
    return N * M // gcd(N, M)

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

# print(N, M, L, n, m, S, T)

ans = True
for i in range(L):
    if i % n == 0 and i % m == 0:
        s = S[i // n]
        t = T[i // m]
        if s != t:
            ans = False
            break

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

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
N, M = map(int, input().split())
S = input()
T = input()
L = N*M//gcd(N,M)
memo = []

for i in range(N):
  memo.append(i*L//N)
for i in range(M):
  tmp = i*L//M
  if tmp in memo:
    if S[tmp//(L//N)] == T[i]:
      continue
    else:
      print(-1)
      exit()
print(L)

Submission status: Time Limit Exceeded

Solution code:
# 2019/08/11

from fractions import gcd

n,m=map(int,input().split())
s=input()
t=input()
lcd=(n*m)//gcd(n,m)
x=['' for _ in range(lcd)]
aa=(lcd//n)
bb=(lcd//m)
for i in range(max(n,m)):
    if i<n:
        a=i*aa
        if x[a]==s[i] or x[a]=='':
            x[a]=s[i]
        else:
            print(-1)
            exit()
    if i<m:
        b=i*bb
        if x[b]==t[i] or x[b]=='':
            x[b]=t[i]
        else:
            print(-1)
            exit()
        
print(lcd)