3334. [USACO20 Jan Silver]Loan Repayment

【题目描述】

Farmer John 欠了 Bessie $N$ 加仑牛奶（$1\le N\le 10^{12}$）。他必须在 $K$ 天内将牛奶给 Bessie。但是，他不想将牛奶太早拿出手。另一方面，他不得不在还债上有所进展，所以他必须每天给 Bessie 至少 $M$ 加仑牛奶$(1\le M\le 10^{12})$。

以下是 Farmer John 决定偿还 Bessie 的方式。首先他选择一个正整数 $X$。然后他每天都重复以下过程：

• 1.假设 Farmer John 已经给了 Bessie $G$ 加仑，计算 $\lfloor \frac{N-G}{X} \rfloor$ 的值。令这个数为 $Y$

• 2.如果 $Y$ 小于 $M$，令 $Y$ 等于 $M$

• 3.给 Bessie $Y$ 加仑牛奶。

求 $X$ 的最大值，使得 Farmer John 按照上述过程能够在 $K$ 天后给 Bessie 至少 $N$ 加仑牛奶 $(1\le K\le 10^{12})$。

【输入格式】

只有一行，包含三个满足$ K ⋅ M < N $且以空格分隔的正整数$ N , K , M $。

【输出格式】

只有一个整数，为正整数$ X $的最大值。

【样例输入】

10 3 3

【样例输出】

2

【样例解释】

当$ X = 2 $时 Farmer John 在第一天偿还 Bessie $ 5 $加仑，在接下来的两天中分别偿还$ M = 3 $加仑。

【提示】

对于$ 37\% $的测试数据(测试点$ 1\sim4 $)，满足$ K ≤ 10^5 $。

对于$ 100\% $的测试数据，均满足上文所给出的数据规模。

【来源】

USACO 一月公开赛 Silver 组