2021真题 | 分糖果 luogu-P7909

CSP-J 2021真题-分糖果，数学规律考点，重点考察对于整除和取余运算性质的理解和规律挖掘能力，适合GESP三级及以上考生练习，难度⭐☆，洛谷难度等级普及−。

P7909 [CSP-J 2021] 分糖果

题目要求

题目背景

红太阳幼儿园的小朋友们开始分糖果啦！

题目描述

红太阳幼儿园有 $n$ 个小朋友，你是其中之一。保证 $n \ge 2$。

有一天你在幼儿园的后花园里发现无穷多颗糖果，你打算拿一些糖果回去分给幼儿园的小朋友们。

由于你只是个平平无奇的幼儿园小朋友，所以你的体力有限，至多只能拿 $R$ 块糖回去。

但是拿的太少不够分的，所以你至少要拿 $L$ 块糖回去。保证 $n \le L \le R$。

也就是说，如果你拿了 $k$ 块糖，那么你需要保证 $L \le k \le R$。

如果你拿了 $k$ 块糖，你将把这 $k$ 块糖放到篮子里，并要求大家按照如下方案分糖果：只要篮子里有不少于 $n$ 块糖果，幼儿园的所有 $n$ 个小朋友（包括你自己）都从篮子中拿走恰好一块糖，直到篮子里的糖数量少于 $n$ 块。此时篮子里剩余的糖果均归你所有——这些糖果是作为你搬糖果的奖励。

作为幼儿园高质量小朋友，你希望让作为你搬糖果的奖励的糖果数量（而不是你最后获得的总糖果数量！）尽可能多；因此你需要写一个程序，依次输入 $n, L, R$，并输出你最多能获得多少作为你搬糖果的奖励的糖果数量。

输入格式

输入一行，包含三个正整数 $n, L, R$，分别表示小朋友的个数、糖果数量的下界和上界。

输出格式

输出一行一个整数，表示你最多能获得的作为你搬糖果的奖励的糖果数量。

输入输出样例 #1

输入 #1

7 16 23

输出 #1

6

输入输出样例 #2

输入 #2

10 14 18

输出 #2

8

输入输出样例 #3

输入 #3

见附件中的 candy/candy3.in。

输出 #3

见附件中的 candy/candy3.ans。

说明/提示

【样例解释 #1】

拿 $k = 20$ 块糖放入篮子里。

篮子里现在糖果数 $20 \ge n = 7$，因此所有小朋友获得一块糖；

篮子里现在糖果数变成 $13 \ge n = 7$，因此所有小朋友获得一块糖；

篮子里现在糖果数变成 $6 < n = 7$，因此这 $6$ 块糖是作为你搬糖果的奖励。

容易发现，你获得的作为你搬糖果的奖励的糖果数量不可能超过 $6$ 块（不然，篮子里的糖果数量最后仍然不少于 $n$，需要继续每个小朋友拿一块），因此答案是 $6$。

【样例解释 #2】

容易发现，当你拿的糖数量 $k$ 满足 $14 = L \le k \le R = 18$ 时，所有小朋友获得一块糖后，剩下的 $k - 10$ 块糖总是作为你搬糖果的奖励的糖果数量，因此拿 $k = 18$ 块是最优解，答案是 $8$。

【数据范围】

对于所有数据，保证 $2 \le n \le L \le R \le {10}^9$。

附件：candy.zip

题目分析

本题是一道具有明显提示的数学规律题目，要求我们在一个给定的合法拿糖果区间 $[L, R]$ 范围内找到一个数量 $k$，使得剩下的“作为奖励的糖果数”最多。

解题思路分析：

1. 题目核心诉求：

   • 翻译题目中的冗长分发过程，可以简化为：将一堆数量为 $k$ 的糖果，不断减去 $n$ 直到不够减为止，最后剩下多少个数。
   • 换算出数学语言，就是这 $k$ 块糖果对 $n$ 求余数（k % n）。
   • 我们的最终的任务就是寻找一个整数 $k \in [L, R]$，使得 $k \bmod n$ 最大。

2. 尝试寻找数学规律（思路一：商数对比法）：

   • 我们知道，除数为 $n$ 时，余数的范围是 $0 \sim n-1$。因此，我们能获得的最大奖励必定是一个不超过 $n-1$ 的数。
   • 我们能不能在区间 $[L, R]$ 里凑出这个最大奖励 $n-1$ 呢？这取决于 $L$ 和 $R$ 之间跨越的距离。
   • 我们可以分别算出 $L$ 除以 $n$ 的商，以及 $R$ 除以 $n$ 的商。
   • 情况一： 如果 $L$ 除以 $n$ 的商不等于 $R$ 除以 $n$ 的商（即 L / n != R / n），说明在这个区间 $[L, R]$ 内至少经历了一次能够“发完一整轮”的变化。那么在这个倍数跨越的前一个数，它刚好差 $1$ 就能发完完整的一轮，其除以 $n$ 的余数绝对是最大值 $n-1$。此时，我们就可以确定在可选拿糖果的数量中，一定能够存在余数最大值 $n - 1$，所以直接输出 $n - 1$ 即可。
   • 情况二： 如果 $L$ 除以 $n$ 的商等于 $R$ 除以 $n$ 的商（即 L / n == R / n），说明在起点 $L$ 到终点 $R$ 的这一段过程中，都没碰到能够再次把一轮分完的“天花板”（即 $n$ 的倍数）。因此，在同一区间内没有完成新的一轮，拿到原先的糖果越多，最后能够剩下分发出的奖励就越多。由于 $k$ 最大能够取到 $R$，所以最大的奖励糖果在此时一定就是 $R \bmod n$。

3. 另一种数学视角（思路二：余数增长法）：

   • 探究可拿糖果的变化空间跨度（即 sub = R - L），并结合起点 $L$ 自身的基础余数（即 L % n）来分析。
   • 当跨度空间极大时（sub >= n）： 我们拥有的选择范围超过了一个完整的分配周期 $n$。这意味着不管起点在哪，在 $L \sim R$ 的范围内必定会经过一个“能平分完糖果然后重新计算余数”的分界点。在刚刚到达分界点之前，必然会经历余数积累并达到最大值 $n - 1$。
   • 当跨度空间不够一整轮时（sub < n）： 我们计算基于起点 $L$ 的基础余数 l_mod = L % n 和极限选择增量的叠加，得到一个理论最大潜力值 l_mod_sum = l_mod + sub。
     • 如果 l_mod_sum >= n：这说明增加的糖量使得总量刚好跨过了下一轮的分界点。中途必然会先达到余数天花板产生极限情况 $n - 1$。
     • 如果 l_mod_sum < n：说明即使我们拿取最多的糖果（增加至 $R$），也到达不了下一个能够清空重算余数的分界点。那在这一段纯粹的攀升过程中，肯定是拿得越多最终余数越大。这时的最大奖励糖果正好就是这个累积总量 l_mod_sum。

4. 时间复杂度优化：

   • 如果我们使用 for 循环从 $L$ 遍历到 $R$ 来逐一比对取最大值，由于最大的 $R - L$ 可达 $10^9$，暴力枚举必然会遭遇超时（TLE）。
   • 但是在掌握了上面的数学性质之后，只要一个 if - else 条件判断加一次余数运算就可以解决问题，时间复杂度被跨越式地优化到了 $O(1)$ 的最佳境界。无论数据范围达到了多少，程序总能在瞬间给出正确答案。

示例代码

C++ 解法一：商数对比法

#include <iostream>

int main() {
    int n, L, R;
    std::cin >> n >> L >> R;

    // 步骤 1：判断区间 [L, R] 内部是否有横跨 n 的整倍数的分界点
    // 通过对比最小值和最大值对应 n 的商是否相同即可判断
    if (L / n != R / n) {
        // 如果不一致，说明中间一定有一个时刻余数能够积累到最大值 (n - 1)
        std::cout << n - 1 << std::endl;
    } else {
        // 如果一致，说明整个获取糖果选项都在没跨过分界线的同一周期内
        // 这个周期内获取糖果越多，剩下的自然余数也就越多
        // 所以我们直接取可能范围内最大的值 R，此时对应的余数也是最大
        std::cout << R % n << std::endl;
    }

    return 0;
}

C++ 解法二：余数增长法

#include <iostream>

int main() {
    int n, L, R;
    std::cin >> n >> L >> R;

    int ans;
    int sub = R - L; // 计算可供选择拿取糖果数量的变化空间（跨度）

    if (sub >= n) {
        // 如果跨度长于或等于一个完整的分配周期 n
        // 那么这期间必然会经过余数循环清零的分界点，而在清零前余数必定为最大极限值 (n - 1)
        ans = n - 1;
    } else {
        // 如果跨度小于一个分配周期 n，也就是不够凑出新的一轮
        int l_mod = L % n;           // 最小值 L 在分配后原本能剩下的基础余数
        int l_mod_sum = l_mod + sub; // 拿最多的糖果时，理论上余数跟着叠加了增加的幅度 sub

        if (l_mod_sum >= n) {
            // 如果叠加后的最终余量达到了周期 n，意味着后来增加的糖果导致又凑够了完整的一轮
            // 其内在必定经历了一次越界前余数顶格的时刻（取得最大值 n - 1）
            ans = n - 1;
        } else {
            // 如果拿取最大空间也没有触及到新一轮的分界线（也就是没有引发被小朋友分走）
            // 那么自然是体力越好拿得越多，剩下的奖励就越大，此时直接取得最大余量
            ans = l_mod_sum; // 其实也就等效于 R % n
        }
    }
    std::cout << ans << std::endl;

    return 0;
}

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号