Problem2049--余数最大化

2049: 余数最大化

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 272  Solved: 129
[Status] [Submit] [Creator:]

Description

给你两个整数 L 和 R(1 ≤ L ≤ R ≤ 1,000,000,000)范围内(包括 L 和 R)找到一个整数,使得这个整数除以整数 n 的余数尽可能地大。

求可能得到的最大的余数。

Input

输入共一行,包含三个整数 L、R、n,两两之间以一个空格分隔(1 ≤ L ≤ R ≤ 1,000,000,000, 1 ≤ n ≤ 1,000,000,000)。

Output

输出一个整数,表示 L 到 R 范围内的所有整数除以 n 的余数的最大值。

Sample Input Copy

10 15 5

Sample Output Copy

4

HINT

样例解释:
取整数 14,14 ÷ 5 = 2 …… 4,能够得到最大的余数 4 。

数据规模与约定:
对于 50% 的数据,L,R,n ≤ 1,000
对于 80% 的数据,L,R,n ≤ 1,000,000
对于 100% 的数据,1 ≤ L ≤ R ≤ 1,000,000,000, 1 ≤ n ≤ 1,000,000,000

Source/Category