Loan Repayment

题目描述

农夫约翰欠贝茜 $N$ 加仑牛奶（$1\le N\le 10^{12}$）。他必须在 $K$ 天内把牛奶给她。然而，他不想太快把牛奶送出去。另一方面，他又必须在还款上持续推进，因此他每天必须至少给贝茜 $M$ 加仑牛奶（$1\le M\le 10^{12}$）。

以下是农夫约翰决定如何还款的方式。他首先选择一个正整数 $X$。然后他每天重复如下过程： 假设农夫约翰已经给了贝茜 $G$ 加仑，计算 $\frac{N-G}{X}$ 向下取整。将这个数记为 $Y$。 如果 $Y$ 小于 $M$，则令 $Y=M$。 给贝茜 $Y$ 加仑牛奶。

确定最大的 $X$，使得如果农夫约翰遵循上述过程，那么在 $K$ 天后他给贝茜的牛奶总量至少为 $N$ 加仑（$1\le K\le 10^{12}$）。

输入格式

输入仅一行，包含三个用空格分隔的正整数 $N$、$K$ 和 $M$，并满足 $K\cdot M<N$。

输出格式

输出最大的正整数 $X$，使得农夫约翰使用上述过程给贝茜的牛奶总量至少为 $N$ 加仑。

10 3 3

2

提示

评分： 测试点 2-4 满足 $K\le 10^5$。 测试点 5-11 没有额外限制。

对于第一个测试用例，当 $X=2$ 时，农夫约翰第一天给贝茜 $5$ 加仑，接下来两天每天给 $M=3$ 加仑。

注意：本题中涉及的整数规模很大，可能需要使用 64 位整数数据类型（例如 C/C++ 中的 "long long"）。 题目致谢：Nick Wu

标签: USACO|2020|Silver

来源

USACO|2020|Silver