自动搬运

查看原文

来自洛谷，原作者为

	滑_稽 主业：原神 副业：其他

搬运于2025-08-24 22:34:10，当前版本为作者最后更新于2021-10-23 23:10:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

0 前言

这道题是两年来我做过的代码量最少的一道普及组题目，考场上 $\text{10min}$ 推出结果，$\text{100pts}$ 应该没问题。（三个样例都过了，你谷民间数据也没错）

1 简化题意

给定正整数 $n,L,R(2\le n\le L\le R\le10^9)$，求 $\max\limits_{k\in[L,R]}\{k\bmod n\}$。

2 题目分析

拿到手，发现这是一道明显的幼儿园高质量小朋友求偶人类高质量女性数学结论题。

$R-L\le 10^9$

明显 $O(n)$ 的做法不可取，怎么办？

自然地想到分析 $L,R$ 与 $n$ 之间的倍数关系。（因为要使 $k\bmod n$ 最大，就一定要找尽量大的小于 $n$ 的倍数的数）

记 $l=\left\lfloor\dfrac{L}{n}\right\rfloor,r=\left\lfloor\dfrac{R}{n}\right\rfloor$，容易发现如果 $l=r$ 的话，$[L,R]$ 里面从小到大所有数模 $n$ 的值是单调递增的，于是 $k=R$ 时 $k\bmod n$ 最大。

如果 $l<r$，说明在 $(L,R]$ 中有至少一个 $n$ 的倍数（记为 $N$）。显然，当 $k=N-1$ 时，$k\bmod n$ 最大，为 $n-1$。

可以结合样例理解上述结论。

3 代码实现

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

int n,l,r;

int main(){
	cin>>n>>l>>r;
	if(l/n==r/n) cout<<r%n;
	else cout<<n-1;
	return 0;
}