[CSP-J 2021] 分糖果

GitHub跳转原题关系图返回列表

把奖励看成 k mod n，按整除块判断区间内能否取到 n-1。

OJ: luogu

题目 ID: P7909

难度:普及-

标签:数学模拟

日期: 2026-06-18 21:17

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

你可以选择拿 k 块糖，其中 L<=k<=RL <= k <= R。 之后每次只要篮子里不少于 n 块糖，所有 n 个小朋友就各拿 1 块。 最后剩下不足 n 块的糖都归你作为奖励，要求奖励数量最大。

思路

先看一个可以直接验证想法的朴素解：

直接枚举 k=L..Rk = L..R，逐个计算最后的奖励值，取最大值。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n, l, r;
    cin >> n >> l >> r;

    long long ans = 0;
    for (long long k = l; k <= r; k++) {
        ans = max(ans, k % n);
    }

    cout << ans << '\n';
    return 0;
}

关键观察是：最后奖励的糖果数，其实就是 k mod n。

因此题目变成：

在区间 [L, R] 中，k mod n 的最大值是多少？

把整数按长度为 n 的块来看：

text
[0..n-1], [n..2n-1], [2n..3n-1], ...

如果 L 和 R 在同一个块里，那么余数从左到右递增，最大值就是 R mod n。 如果它们跨过了块边界，那么区间里一定能取到余数 n-1，这已经是最大可能值。

代码

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

long long solve(long long n, long long l, long long r) {
    if (l / n == r / n) return r % n;
    return n - 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n, l, r;
    cin >> n >> l >> r;
    cout << solve(n, l, r) << '\n';
    return 0;
}

复杂度

主解只做常数次计算，时间复杂度 O(1)O(1)，空间复杂度 O(1)O(1)。

总结

这题的关键是把“分糖果过程”直接识别成“取模”。