Problem:


Score : 400 points

Problem Statement

You are given integers N and M.

Consider a sequence a of length N consisting of positive integers such that a_1 + a_2 + ... + a_N = M. Find the maximum possible value of the greatest common divisor of a_1, a_2, ..., a_N.

Constraints

All values in input are integers.

1 \leq N \leq 10^5

N \leq M \leq 10^9

Input

Input is given from Standard Input in the following format:

N M

Output

Print the maximum possible value of the greatest common divisor of a sequence a_1, a_2, ..., a_N that satisfies the condition.

Sample Input 1

3 14

Sample Output 1

2

Consider the sequence (a_1, a_2, a_3) = (2, 4, 8). Their greatest common divisor is 2, and this is the maximum value.

Sample Input 2

10 123

Sample Output 2

3

Sample Input 3

100000 1000000000

Sample Output 3

10000



Sample input:
3 14


Sample output:
2

Submission status: Runtime Error

Solution code:
from sympy import divisors

n,m = map(int,input().split())
l = m//n
a = list(divisors(m,generator=True))
c = 0

for i in range(len(a)):
    if a[i] > c and a[i] <= l:
        c = a[i]

print(c)

Submission status: Runtime Error

Solution code:
import math
tmp=raw_input().split(" ")
N=int(tmp[0])
M=int(tmp[1])
dvd=[]
while i<=math.sqrt(M):
  if M%i==0:
    dvd.append(i)
  i=i+1
for j in len(dvd):
  sum=M/dvd[len(dvd)-j-1]
  if sum<N:
    pass
  else:
    sum>=N:
      print dvd[len(dvd)-j-1]

Submission status: Runtime Error

Solution code:
import math
N,M=map(int,input().split())
s=M//N
L=math.sqrt(M)
l=math.floor(L)
a=[]
for i in range(1,l+2):
    d=M/i 
    if d.is_integer()==True:
        a.append(i)
        a.append(d)
b=list(filter(lambda x:x<s, a))
c=max(b)
print(c)

Submission status: Runtime Error

Solution code:
inp = list(map(int, input().split()))
N, M = inp[0], inp[1]

num = M // N

ls = list(range(1, num+1))[::-1]
if N == M:
    print(1)
elif N/2 == M:
    print(2)
else:
    for k in ls:
        if M % k == 0:
            print(k)
            break

Submission status: Runtime Error

Solution code:
import math

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

x=math.floor(m/n)

ans=[]
for i in range(2,x+1):
  if(m % i==0):
    ans.append(i)

ans.sort()
ans.reverse()
print(ans[0])

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
print(max(i for i in range(2, 100000) if m % i == 0 and m / i >= n))

Submission status: Runtime Error

Solution code:

import sys
from collections import deque
import copy

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def make_divisor_list(num):
    if num < 1:
        return []
    elif num == 1:
        return [1]
    else:
        divisor_list = []
        divisor_list.append(1)
        for i in range(2, min(num // 2, 100000) + 1):
            if num % i == 0:
                divisor_list.append(i)
        divisor_list.append(num)

        return divisor_list


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] = [int(input_raw[0]), int(input_raw[1])]

    for num in range(M/N, 0, -1):
        if M % num == 0 and M/num >= N:
            print num
            exit()


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from sympy import divisors
n,m = map(int,input().split())
l = m//n
a = list(divisors(m,generator=True))
c = 0

for i in range(len(a)):
    if a[i] > c and a[i] <= l:
        c = a[i]

print(c)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
def divisor_gen(n,m):
  l=[]
  o=[]
  for i in range(2, int(n*(1/2)+1):
    if n%i == 0:
      l.append(i)
  l.append(m)
  for i in l:
    if n>=m/i:
      o.append(i)
  print(max(o))
divisor_gen(n,m)

Submission status: Runtime Error

Solution code:
def factorize(n):
    fct = []  
    b, e = 2, 0  
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct


def divisorize(fct):
    b, e = fct.pop() 
    pre_div = divisorize(fct) if fct else [[]]
    suf_div = [[(b, k)] for k in range(e + 1)]
    return [pre + suf for pre in pre_div for suf in suf_div]

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

re = 1
fa = factorize(M)
div_list = divisorize(fa)

for i in range(len(div_list)):
    num = 1
    for j in range(len(div_list[-1 - i])):
        l = div_list[-1-i][j]
        num *= l[0] ** l[1]
    d = M // num 
    if d >= N and num > re:
        re = num
print(re)

Submission status: Runtime Error

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

if M % N == 0:
    print(M//N)
else:
    print(math.gcd((M//N), (M%N)))

Submission status: Runtime Error

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

def warizan(n,m):
    if m % n == 0:
        print(m // n)
        exit()
    warizan(n+1,m)

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

warizan(N,M)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Oct  6 21:37:39 2018

@author: ogura
"""
import math

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

for i in range(10000):
    a = math.gcd(m, i)
    if a == 1:
        continue
    tmp = int(a *(1 - a ** n) // (1 - a))
    if tmp == m:
        break

print(a)

Submission status: Runtime Error

Solution code:
import math
import bisect
N, M = map(int, input().split())
rootM = math.sqrt(M)

factors = set()
for i in range(1, math.ceil(rootM)):
  if M % i == 0:
    factors.add(i)
    factors.add(M // i)
factarr = sorted(list(factors))
print(M // factarr[bisect.bisect_left(factarr, N)])

Submission status: Runtime Error

Solution code:
%%time
n, m = map(int, '3 1000000000'.split())
if (m > 1e8) and (m%1000==0):
    max_itr = m//n
    for i in range(max_itr, 0, -100):
        if m%round(i, -2)==0:
            break
    print(round(i, -2))
else:
    max_itr = m//n
    for i in range(max_itr, 0, -1):
        if m%i==0:
            break
    print(i)

Submission status: Runtime Error

Solution code:
import sympy
n,m = map(int,input().split())
l = m//n
a = list(sympy.divisors(m,generator=True))
c = 0
for i in range(1,len(a)):
    if a[i] > c and a[i] <= l:
        c = a[i]

print(c)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Oct  6 21:37:39 2018

@author: ogura
"""
import math

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

for i in range(10000):
    a = math.gcd(m, i)
    if a == 1:
        continue
    tmp = int(a *(1 - a ** n) // (1 - a))
    if tmp == m:
        break

print(a)

Submission status: Runtime Error

Solution code:
N, M = map(int, raw_input().split())

for i in range(1, int(M/N)+1)[::-1]:
    if M%i == 0:
        print i
        break

Submission status: Runtime Error

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

a = int(M/N)

if M % 2 == 0:
    m = M / 2
    a =  int(a/2) + 1

for i in range(a,0,-1):
    if m % i == 0:
        c = i
        break

if c == 1 and M % 2 == 0:
    c = 2

print(c)

Submission status: Runtime Error

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

a = int(M/N)

if M % 2 == 0:
m = M / 2
a =  int(a/2) + 1

for i in range(a,0,-1):
    if m % i == 0:
        c = i
        break

if c == 1 and M % 2 == 0
    c = 2
    
print(c)

Submission status: Runtime Error

Solution code:
from itertools import product
from collections import OrderedDict

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

m = M//N

# def prime_factors(n):
#     i = 2
#     factors = OrderedDict()
#     while i * i <= n:
#         if n % i:
#             i += 1
#         else:
#             n //= i
#             if i in factors:
#               factors[i] += 1
#             else:
#               factors[i] = 1
#     if n > 1:
#       if n in factors:
#         factors[n] += 1
#       else:
#         factors[n] = 1
#     return factors

def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct


def divisorize(fct):
    b, e = fct.pop()  # base, exponent
    pre_div = divisorize(fct) if fct else [[]]
    suf_div = [[(b, k)] for k in range(e + 1)]
    return [pre + suf for pre in pre_div for suf in suf_div]


def num(fct):
    a = 1
    for base, exponent in fct:
        a = a * base**exponent
    return a

fct = factorize(M)
current_n = 1

for div in divisorize(fct):
    n = num(div)
    if n <= m and current_n < n:
      current_n = n

print(current_n)

# for x in range(m, 0, -1):
#   if M % x == 0:
#     print(x)
#     break

Submission status: Runtime Error

Solution code:
import functools, itertools, fractions
N, M = [int(x) for x in input().split()]
def gcd(x):
    return functools.reduce(fractions.gcd, x)
print(gcd(max(filter(lambda x: sum(x) == M, itertools.combinations(range(1, M), N)), key=gcd)))

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
if m%2:
    for i in range(m//n, 0, -2):
    if not m%i:
        print(i)
        break
else:
    for i in range(m//n, 0, -1):
        if not m%i:
            print(i)
            break

Submission status: Runtime Error

Solution code:
import functools, itertools, fraction
N, M = [int(x) for x in input().split()]
def gcd(x):
    return functools.reduce(fraction.gcd, x)
print(gcd(max(filter(lambda x: sum(x) == M, itertools.combinations(range(1, M), N)), key=gcd)))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
m = M
prime = []
flg = True
while flg:
    for i in range(2, m+1):
        if m % i == 0:
            m /= i
            prime.append(i)
            if m == 1:
                flg = False
res = 1
for i in prime:
    if i * N <= M:
        res = i
print(res)

Submission status: Runtime Error

Solution code:
# coding:utf-8
def inpl(): return list(map(int, input().split()))
N, M = inpl()
i = 2
tmp = []
MM = M
while i * i <= MM:
    if MM % i == 0:
        tmp.append(i)
        while MM % i == 0:
            MM //= i
    i += 1
if MM != 1:
    tmp.append(MM)
n = M // N
sub = tmp[0]
while n > 0:
    if M % n == 0:
        print(n)
        break
    else:
        n -= sub

Submission status: Runtime Error

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

def dividable(x,y):
    if x/y == x//y:
        return True
    else:
        return False

for i in range(2,int(M//N)+1):
    if dividable(M,i) and int(M/i) >= N:
            answer = i

print(answer)

Submission status: Runtime Error

Solution code:
#M%N=0なら、M/Nが回答
#そうでないとき、MのM/Nより小さく、最大の公約数を探して
#それをSとしたとき、S*N<MならSが回答
#これを延々とやれば、最小でも1が回答になる。

n,m = map(int,input().split())
if m%n==0:
    print(m/n)
    exit()
s = m//n
while(True):
    s = s-1
    if m%s == 0:
        if s*n < m:
            print(s)
            break

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split(" "))
div1 = []
div2 = []

for i in range(1, int(math.sqrt(M))+1):
    if M % i == 0:
        div1 += (i,)
        div2 += (M//i,)
for d in div2:
    if d * N <= M:
        print(d)
        break
else:
    div1 = div1[::-1]
    for d in div1:
        if d * N <= M:
            print(d)
            break

Submission status: Runtime Error

Solution code:
import math

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

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

g=math.gcd(a,a+b)
print(g)

Submission status: Runtime Error

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

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

for i in range(a-b,0,-1):
    if M % i == 0:
        c = i
        break

print(c)

Submission status: Runtime Error

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

if N == 1:
    print(M)

elif M % 2 == 1:
    if M // N % 2 == 0:
        if M % (M//N) == 0:
            if M / (M//N) >= N:
                print(M//N)
                break
        else:
            for i in range(M//N - 1, 0, -2):
                if M % i == 0:
                    if M / i >= N:
                        print(i)
                        break
    else:
        for i in range(M//N, 0, -2):
            if M % i == 0:
                if M / i >= N:
                    print(i)
                    break
else:
    for i in range(M // N, 0, -1):
        if M % i == 0:
            if M / i >= N:
                print(i)
                break

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
l=[]
o=[]
for i in range(1,m+1):
  if m%i==0:
    l.append(i)
for i in l:
  if n>=m/l[i]:
    o.append(l[i])
print(max(o))

Submission status: Runtime Error

Solution code:
from math import sqrt, floor
import sys

N, M = map(int, input().split())
rootM = floor(sqrt(M))

for m in reversed(range(rootM)):
    if M % m == 0:
        if M // m >= N:
            print(m)
            sys.exit()

Submission status: Runtime Error

Solution code:
import numpy as np
def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct


def divisorize(fct):
    b, e = fct.pop()  # base, exponent
    pre_div = divisorize(fct) if fct else [[]]
    suf_div = [[(b, k)] for k in range(e + 1)]
    return [pre + suf for pre in pre_div for suf in suf_div]

def num(fct):
    a = 1
    for base, exponent in fct:
        a = a * base**exponent
    return a
def yaku(n):
    fct = factorize(n)
    y = divisorize(fct)
    ys = []
    for yy in y:
        ys.append(num(yy))
    ys.sort()
    return ys

n,m = list(map(int,input().split()))
y = yaku(m)
print(np.max(np.array(y)[np.array(y) <= m/n]))

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
s=M//N 

for i in range(s,0,-1):
    d=M/i 
    if d.is_integer()==True
        k=i
        break
print(i)

Submission status: Runtime Error

Solution code:
import numpy as np
def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct


def divisorize(fct):
    b, e = fct.pop()  # base, exponent
    pre_div = divisorize(fct) if fct else [[]]
    suf_div = [[(b, k)] for k in range(e + 1)]
    return [pre + suf for pre in pre_div for suf in suf_div]

def num(fct):
    a = 1
    for base, exponent in fct:
        a = a * base**exponent
    return a
def yaku(n):
    fct = factorize(n)
    y = divisorize(fct)
    ys = []
    for yy in y:
        ys.append(num(yy))
    ys.sort()
    return ys

n,m = list(map(int,input().split()))
y = yaku(m)
np.max(np.array(y)[np.array(y) <= m/n])

Submission status: Runtime Error

Solution code:
import math

N,M = map(int,input().split())
A = M//N
L = []
flag = False
if (A <= 10**8):
  for i in range(1,A+1):
    if (M%(A+1-i) == 0):
      flag = True
      break
  if flag:
    print(A+1-i)
else:
  for i in range(1,math.sqrt(A)):
    if (M%i == 0):
      L.append(i)
  print(max(L))

Submission status: Runtime Error

Solution code:
inp = list(map(int, input().split()))
N, M = inp[0], inp[1]

num = M // N
l = list(range(1, num+1))[::-1]

for k in l:
    if M % k == 0:
        print(k)
        break

Submission status: Runtime Error

Solution code:



def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct


def divisorize(fct):
    b, e = fct.pop()  # base, exponent
    pre_div = divisorize(fct) if fct else [[]]
    suf_div = [[(b, k)] for k in range(e + 1)]
    return [pre + suf for pre in pre_div for suf in suf_div]


def num(fct):
    a = 1
    for base, exponent in fct:
        a = a * base**exponent
    return a


x,n = map(int,input().split())
fct = factorize(n)


divlist=[]
for div in divisorize(fct):
    divlist.append(num(div))

divlist.sort()
ans = 1
for i in range(0,len(divlist)):
    if divlist[i] <= n/x:
        ans = divlist[i]
print(ans)

Submission status: Runtime Error

Solution code:
#112D
N,M=map(int,input().split())
for i in list(range(1,M//N+1))[::-1]:
    flag=M-N*i
    if flag%i==0 and flag>=0:
        print(i)
        break

Submission status: Runtime Error

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

ma = m//n
re = m%n

flag=0

if re==0:
    while(flag==0):
        if m%ma==0:
            print(ma)
            flag = 1
        ma -=1
else:
    flag2=0
    while(flag==0):
        if m%ma==0:
            print(ma)
            flag = 1
            
        if flag2==0:
            ma -=1
            if ma%re==0:
                flag2=1
        
        else:
            ma -= re

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
for i in range(1, m):
    if m % i == 0:
        if m // i >= n:
            ans = i
        else:
            break
print(ans)

Submission status: Runtime Error

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

def primefactorize(n):
    fct = []  # return [[p1, power1], [p2, power2], ...]
    p, power = 2, 0
    while p * p <= n:
        while n % p == 0:
            n = n // p
            power += 1
        if power > 0:
            fct.append([p, power])
        if p == 2:
            p += 1
        else:
            p += 2
        power = 0
    if n > 1:
        fct.append([n, 1])
    return fct

def divisorize(fct):
    b, e = fct.pop()  # base, exponent
    pre_div = divisorize(fct) if fct else [[]]
    suf_div = [[(b, k)] for k in range(e + 1)]
    return [pre + suf for pre in pre_div for suf in suf_div]

def num(fct):
    a = 1
    for base, exponent in fct:
        a = a * base**exponent
    return a

fct = primefactorize(M)
factors = []
for div in divisorize(fct):
    factors.append(num(div))

factors.sort()
k = M//N
L = [x for x in factors if x <= k]
print(max(L))

Submission status: Runtime Error

Solution code:
import math
n,m = map(int,input().split())
MAX = m//n
ans = 1
def factorization(n):
    def factor_sub(n, m):
        c = 0
        while n % m == 0:
            c += 1
            n /= m
        return c, n
    #
    buff = []
    c, m = factor_sub(n, 2)
    if c > 0: buff.append((2, c))
    c, m = factor_sub(m, 3)
    if c > 0: buff.append((3, c))
    x = 5
    while m >= x * x:
        c, m = factor_sub(m, x)
        if c > 0: buff.append((x, c))
        if x % 6 == 5:
            x += 2
        else:
            x += 4
    if m > 1: buff.append((m, 1))
    return buff
def divisor_sub(p, q):
    a = []
    for i in range(0, q + 1):
        a.append(p ** i)
    return a

def divisor(n):
    xs = factorization(n)
    ys = divisor_sub(xs[0][0], xs[0][1])
    for p, q in xs[1:]:
        ys = [x * y for x in divisor_sub(p, q) for y in ys]
    return sorted(ys)
a = divisor(m)
for i in a:
  if i <= MAX:
    ans = i
print(ans)

Submission status: Runtime Error

Solution code:
[n,m] = [int(i) for i in input().split()]
a=[]
import math
for i in range(1,math.floor(m**(1/2))):
    if m % i == 0 and i <= m//n:
        a.append(i)

print(a[len(a)-1])

Submission status: Runtime Error

Solution code:
import math
from functools import reduce
import collections
import itertools
import sympy
a = list(map(int,input().split()))
n = a[0]
m= a[1]
yaku = []
for i in range(1,m+1):
    if m % i == 0:
        if i >= n:
            print(int(m/i))
            break

Submission status: Runtime Error

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(1000000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]


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


def gcd_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = gcd(v, L[i])

    return v


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


def lcm_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = lcm(v, L[i])

    return v


# Width First Search (+ Distance)
def wfs_d(D, N, K):
    """
    D: 隣接行列(距離付き)
    N: ノード数
    K: 始点ノード
    """

    dfk = [-1] * (N + 1)
    dfk[K] = 0

    cps = [(K, 0)]
    r = [False] * (N + 1)
    r[K] = True
    while len(cps) != 0:
        n_cps = []
        for cp, cd in cps:
            for i, dfcp in enumerate(D[cp]):
                if dfcp != -1 and not r[i]:
                    dfk[i] = cd + dfcp
                    n_cps.append((i, cd + dfcp))
                    r[i] = True

        cps = n_cps[:]

    return dfk


# Depth First Search (+Distance)
def dfs_d(v, pre, dist):
    """
    v:  現在のノード
    pre: １つ前のノード
    dist: 現在の距離

    以下は別途用意する
    D: 隣接リスト(行列ではない)
    D_dfs_d: dfs_d関数で用いる，始点ノードから見た距離リスト
    """

    global D
    global D_dfs_d

    D_dfs_d[v] = dist

    for next_v, d in D[v]:
        if next_v != pre:
            dfs_d(next_v, v, dist + d)

    return


def sigma(N):
    ans = 0
    for i in range(1, N + 1):
        ans += i
    return ans


def comb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def bisearch(L, target):
    low = 0
    high = len(L) - 1
    
    while low <= high:
        mid = (low + high) // 2
        guess = L[mid]
        if guess == target:
            return True
        elif guess < target:
            low = mid + 1
        elif guess > target:
            high = mid - 1
    if guess != target:
        return False

# --------------------------------------------

dp = None

def main():
    N, M = li_input()

    x = M // N
    ans = -1

    if N == 1:
        print(M)
        return

    if M == 10 ** 9:
        if N == 2:
            print(500000000)
            return
        if N == 3 or N == 4:
            print(250000000)
            return
        if N == 5:
            print(200000000)
            return


    for i in range(x, 0, -1):
        j = M - (i * (N - 1))

        ans = max(ans, math.gcd(i, j))

        if i - 1 < ans:
            break

    print(ans)

main()

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
for i in range(1, M):
    if M / i < N:
        break
    if M % i == 0:
        ans = i
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(1000000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]


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


def gcd_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = gcd(v, L[i])

    return v


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


def lcm_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = lcm(v, L[i])

    return v


# Width First Search (+ Distance)
def wfs_d(D, N, K):
    """
    D: 隣接行列(距離付き)
    N: ノード数
    K: 始点ノード
    """

    dfk = [-1] * (N + 1)
    dfk[K] = 0

    cps = [(K, 0)]
    r = [False] * (N + 1)
    r[K] = True
    while len(cps) != 0:
        n_cps = []
        for cp, cd in cps:
            for i, dfcp in enumerate(D[cp]):
                if dfcp != -1 and not r[i]:
                    dfk[i] = cd + dfcp
                    n_cps.append((i, cd + dfcp))
                    r[i] = True

        cps = n_cps[:]

    return dfk


# Depth First Search (+Distance)
def dfs_d(v, pre, dist):
    """
    v:  現在のノード
    pre: １つ前のノード
    dist: 現在の距離

    以下は別途用意する
    D: 隣接リスト(行列ではない)
    D_dfs_d: dfs_d関数で用いる，始点ノードから見た距離リスト
    """

    global D
    global D_dfs_d

    D_dfs_d[v] = dist

    for next_v, d in D[v]:
        if next_v != pre:
            dfs_d(next_v, v, dist + d)

    return


def sigma(N):
    ans = 0
    for i in range(1, N + 1):
        ans += i
    return ans


def comb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def bisearch(L, target):
    low = 0
    high = len(L) - 1
    
    while low <= high:
        mid = (low + high) // 2
        guess = L[mid]
        if guess == target:
            return True
        elif guess < target:
            low = mid + 1
        elif guess > target:
            high = mid - 1
    if guess != target:
        return False

# --------------------------------------------

dp = None

def main():
    N, M = li_input()

    x = M // N
    ans = -1

    if N == 1:
        print(M)
        return

    if M == 10 ** 9:
        if N == 2:
            print(500000000)
        if N == 3 or N == 4:
            print(250000000)
        if N == 5:
            print(200000000)


    for i in range(x, 0, -1):
        j = M - (i * (N - 1))

        ans = max(ans, math.gcd(i, j))

        if i - 1 < ans:
            break

    print(ans)

main()

Submission status: Runtime Error

Solution code:
# Thanks for http://nihaoshijie.hatenadiary.jp/entry/2018/02/03/115759

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


def factorize(n):
    fct = []
    b, e = 2, 0
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct

def divisorize(fct):
    b, e = fct.pop()
    pre_div = divisorize(fct) if fct else [[]]
    suf_div = [[(b, k)] for k in range(e + 1)]
    return [pre + suf for pre in pre_div for suf in suf_div]

def num(fct):
    a = 1
    for base, exponent in fct:
        a = a * base**exponent
    return a


fct = factorize(M)
L   = []
for div in divisorize(fct):
    L.append(num(div))

L.sort()
L.reverse()

for l in L:
    if l * N <= M and M % l == 0:
        print(l)
        break

Submission status: Runtime Error

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

def primefactorize(n):
    fct = []  # return [[p1, power1], [p2, power2], ...]
    p, power = 2, 0
    while p * p <= n:
        while n % p == 0:
            n = n // p
            power += 1
        if power > 0:
            fct.append([p, power])
        if p == 2:
            p += 1
        else:
            p += 2
        power = 0
    if n > 1:
        fct.append([n, 1])
    return fct

def divisorize(fct):
    b, e = fct.pop()  # base, exponent
    pre_div = divisorize(fct) if fct else [[]]
    suf_div = [[(b, k)] for k in range(e + 1)]
    return [pre + suf for pre in pre_div for suf in suf_div]

def num(fct):
    a = 1
    for base, exponent in fct:
        a = a * base**exponent
    return a

fct = primefactorize(M)
factors = []
for div in divisorize(fct):
    factors.append(num(div))

factors.sort()
cd = 0
k = M/N
for x in factors:
    if x <= k:
        cd = max(cd, x)
print(cd)

Submission status: Runtime Error

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect
import fraction

# Set max recursion limit
sys.setrecursionlimit(1000000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]


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


def gcd_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = gcd(v, L[i])

    return v


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


def lcm_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = lcm(v, L[i])

    return v


# Width First Search (+ Distance)
def wfs_d(D, N, K):
    """
    D: 隣接行列(距離付き)
    N: ノード数
    K: 始点ノード
    """

    dfk = [-1] * (N + 1)
    dfk[K] = 0

    cps = [(K, 0)]
    r = [False] * (N + 1)
    r[K] = True
    while len(cps) != 0:
        n_cps = []
        for cp, cd in cps:
            for i, dfcp in enumerate(D[cp]):
                if dfcp != -1 and not r[i]:
                    dfk[i] = cd + dfcp
                    n_cps.append((i, cd + dfcp))
                    r[i] = True

        cps = n_cps[:]

    return dfk


# Depth First Search (+Distance)
def dfs_d(v, pre, dist):
    """
    v:  現在のノード
    pre: １つ前のノード
    dist: 現在の距離

    以下は別途用意する
    D: 隣接リスト(行列ではない)
    D_dfs_d: dfs_d関数で用いる，始点ノードから見た距離リスト
    """

    global D
    global D_dfs_d

    D_dfs_d[v] = dist

    for next_v, d in D[v]:
        if next_v != pre:
            dfs_d(next_v, v, dist + d)

    return


def sigma(N):
    ans = 0
    for i in range(1, N + 1):
        ans += i
    return ans


def comb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def bisearch(L, target):
    low = 0
    high = len(L) - 1
    
    while low <= high:
        mid = (low + high) // 2
        guess = L[mid]
        if guess == target:
            return True
        elif guess < target:
            low = mid + 1
        elif guess > target:
            high = mid - 1
    if guess != target:
        return False

# --------------------------------------------

dp = None

def main():
    N, M = li_input()

    x = M // N
    ans = -1

    if N == 1:
        print(M)
        return


    for i in range(x, 0, -1):
        j = M - (i * (N - 1))

        ans = max(ans, fraction.gcd(i, j))

        if i - 1 < ans:
            break

    print(ans)

main()