Contest Duration: ~ (local time) (100 minutes) Back to Home
D - Partition /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

a_1 + a_2 + ... + a_N = M となる正整数からなる長さ N の数列 a において、a_1, a_2, ..., a_N の最大公約数のとり得る最大値を求めてください。

### 制約

• 入力はすべて整数である
• 1 \leq N \leq 10^5
• N \leq M \leq 10^9

### 入力

N M


### 入力例 1

3 14


### 出力例 1

2


(a_1, a_2, a_3) = (2, 4, 8) としたときこれらの最大公約数が 2 となり最大です。

### 入力例 2

10 123


### 出力例 2

3


### 入力例 3

100000 1000000000


### 出力例 3

10000


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