P7909 [CSP-J 2021] 分糖果

题意简述

给定正整数 $2\le n\le L\le R\le 10^9$，求：

$$\max_{k=L}^Rk\bmod n$$

解题思路

将区间 $[L,R]$ 划分为长度为 $n$ 的段，在同一段内 $k\bmod n$ 单调递增，且最大值为 $n-1$。

• 若 $\left\lfloor\frac{L}{n} \right\rfloor=\left\lfloor\frac{R}{n}\right\rfloor$，说明 $[L,R]$ 位于同一段内，取 $k=R$ 时答案为 $R\bmod n$；
• 否则，$[L,R]$ 跨越至少一段，取 $k=n\left\lfloor\frac{R}{n}\right\rfloor-1$ 时答案为 $n-1$。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,l,r;
	cin>>n>>l>>r;
	cout<<(l/n==r/n?r%n:n-1)<<'\n';
	return 0;
}