問題一覧 > 通常問題

No.136 Yet Another GCD Problem

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 302
作問者 : anta
お気に入りにしたユーザー ProblemId : 254 / 自分の提出
問題文最終更新日: 2026-06-26 16:18:53
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 79 (順位表) の他の問題:

Problem Statement

For an array $A$ of positive integers, when the sum of $A$ is exactly $x$, we call $A$ a partition of $x$.

For an array $A$ of integers, we define $\gcd(A) = \gcd(A_1,A_2,\ldots,A_{|A|})$.

You are given integers $N, K$. Over all partitions $A$ of $N$ satisfying $2 \le |A| \le K$, maximize $\gcd(A)$.

Input

N K

The integers $N, K$ ($2 \le N \le 10^5$, $2 \le K \le 10^5$) are given on one line, separated by a space.

Output

Among all $A$ satisfying the conditions in the problem statement, print on one line the value $\gcd(A)$ of an $A$ for which $\gcd(A)$ is maximum.

Sample

Sample 1
Input
21 2
Output
7

For example, if $A = [7,14]$, then $A$ is a partition of $21$, and the greatest common divisor of the elements of $A$ is $\operatorname{gcd}(7,14) = 7$.

Sample 2
Input
23 100000
Output
1

No matter how 23 is split into an array of length 2 or more, the greatest common divisor of its elements is 1.

Sample 3
Input
100 2
Output
50

$A = [50,50]$ is the only partition whose elements have a greatest common divisor of 50.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。