P7909 [CSP-J 2021] 分糖果

结论题

题面概括

请在 $[l,r]$ 中找出一个数 $k$，使得 $n$ % $k$ 的值最大.

思路

当 $n \le 10^9$ 时，说明 $\Theta (n)$ 的算法已经结束了.

所以，接下来是结论推理.

当 $\left \lfloor \frac {l} {n} \right \rfloor = \left \lfloor \frac {r} {n} \right \rfloor$ 时，$r$ % $n$ 的值明显是最大的.

当 $\left \lfloor \frac {l} {n} \right \rfloor < \left \lfloor \frac {r} {n} \right \rfloor$ 时，说明 $[l,r]$ 之间至少有一个 $n$ 的倍数，设这个数为 $x$.显然，当 $k = x$ 时，

不可能时 $n$ % $k$ 的值最大，所以, 当 $k = x-1$，时，$n$ % $k$的值最大.

代码

#include<iostream>
#include<cstdio>
using namespace std;

int n, l, r;

int main() {
	scanf("%d%d%d", &n, &l, &r);
	if (r / n > l / n) printf("%d", n - 1);
	else printf("%d", r % n);
	return 0;
}