题解 P7909 [CSP-J 2021] 分糖果

· · 题解

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;
}