#PU991. USACO 2020 January Contest, Silver — Problem 2. Loan Repayment

    ID: 1529 传统题 文件IO:loan 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高 上传者: 标签>USACO赛事:jan20来源:usaco.orgscoring:equal_test_cases二分答案

USACO 2020 January Contest, Silver — Problem 2. Loan Repayment

USACO 2020 January Contest, Silver — Problem 2. Loan Repayment

题目描述

Farmer John owes Bessie NN gallons of milk (1≤N≤10121\le N\le 10^{12}). He has to give her the milk within KK days. However, he doesn't want to give the milk away too quickly. On the other hand, he has to make forward progress on the loan, so he must give Bessie at least MM gallons of milk each day (1≤M≤10121\le M\le 10^{12}). Here is how Farmer John decides to pay back Bessie. He first picks a positive integer XX. He then repeats the following procedure every day: Assuming that Farmer John has already given Bessie GG gallons, compute N−GX\frac{N-G}{X} rounded down. Call this number YY. If YY is less than MM, set YY to MM. Give Bessie YY gallons of milk. Determine the largest XX such that if Farmer John follows the above procedure, Farmer John gives Bessie at least NN gallons of milk after KK days (1≤K≤10121\le K\le 10^{12}).

输入格式

The only line of input contains three space-separated positive integers NN, KK, and MM satisfying K⋅M<NK\cdot M<N.

输出格式

(见题面原文)

数据范围

Test cases 2-4 satisfy K≤105.K\le 10^5. Test cases 5-11 satisfy no additional constraints.

样例

样例 1

10 3 3
2
For the first test case, when $X=2$ Farmer John gives Bessie $5$ gallons  on the
first day and $M=3$ gallons on each of the next two days.

提示

data types (e.g., a "long long" in C/C++). Problem credits: Nick Wu