这两个问题分别对应了中国计算机学会 CSP-J（入门组）的两道经典算法题。将它们抽象为数学问题，可以帮助我们理清其中的数量关系，从而设计出时空复杂度极佳的算法。

下面分别对这两个问题进行数学抽象与推导。

问题一：拿苹果（数学抽象）

1. 问题建模

设初始苹果数量为 $n$。每天拿走苹果的过程可以看作是一个数列的缩减过程。 令 $n_t$ 表示在第 $t$ 天开始前（或第 $t-1$ 天结束后）剩下的苹果数量，其中初始状态为： $$n_0 = n$$

2. 状态转移方程（每天减少的规律）

在第 $t$ 天，小苞每隔 2 个苹果拿走 1 个（即拿走第 $1, 4, 7, 10, \dots$ 个苹果）。 这一天拿走的苹果数量为： $$\Delta_t = \lceil \frac{n_{t-1}}{3} \rceil = \lfloor \frac{n_{t-1} + 2}{3} \rfloor$$

因此，第 $t$ 天结束后的剩余苹果数量 $n_t$ 为： $$n_t = n_{t-1} - \Delta_t = n_{t-1} - \lfloor \frac{n_{t-1} + 2}{3} \rfloor$$

此递推关系持续进行，直到满足终止条件： $$n_T = 0$$ 此时的 $T$ 即为拿完所有苹果的总天数。由于每次大约减少 $\frac{1}{3}$，总天数 $T$ 的数量级为 $O(\log n)$。

3. 编号为 $n$ 的苹果被拿走的条件

初始编号为 $n$ 的苹果处于队列的最末尾。 在每一天中，由于所有的删除操作都在它左侧或恰好选中它，它在剩余苹果队列中始终保持在最后一个位置。

当且仅当某一天 $t$，剩余的苹果总数 $n_{t-1}$ 满足被 3 除余 1 时，最后一个位置的苹果才会被拿走。即满足： $$n_{t-1} \equiv 1 \pmod 3$$

因此，编号为 $n$ 的苹果被拿走的天数 $D$ 为： $$D = \min { t \mid n_{t-1} \equiv 1 \pmod 3 }$$

4. 数学实例验证 ($n=8$)

• $t=1$：$n_0 = 8 \not\equiv 1 \pmod 3$。拿走 $\lceil 8/3 \rceil = 3$ 个，剩余 $n_1 = 5$ 个。
• $t=2$：$n_1 = 5 \not\equiv 1 \pmod 3$。拿走 $\lceil 5/3 \rceil = 2$ 个，剩余 $n_2 = 3$ 个。
• $t=3$：$n_2 = 3 \not\equiv 1 \pmod 3$。拿走 $\lceil 3/3 \rceil = 1$ 个，剩余 $n_3 = 2$ 个。
• $t=4$：$n_3 = 2 \not\equiv 1 \pmod 3$。拿走 $\lceil 2/3 \rceil = 1$ 个，剩余 $n_4 = 1$ 个。
• $t=5$：$n_4 = 1 \equiv 1 \pmod 3$。满足条件，记录 $D = 5$。拿走 $\lceil 1/3 \rceil = 1$ 个，剩余 $n_5 = 0$。

结果：总天数 $T = 5$，第 $n$ 个苹果在第 $D = 5$ 天被拿走。

问题二：分糖果（数学抽象）

1. 问题建模

我们已知小朋友人数 $n$，糖果数量的选择区间为 $[L, R]$。 分配糖果并保留余数的过程在数学上等价于求模运算。设我们拿了 $k$ 块糖果，奖励给我们的糖果数（余数）为 $f(k)$： $$f(k) = k \bmod n \quad (\text{其中 } k \in [L, R])$$

我们的目标是寻找一个 $k$，使得 $f(k)$ 最大化。即求解： $$\max_{k \in [L, R]} (k \bmod n)$$

2. 分类讨论与推导

模 $n$ 的最大可能余数为 $n-1$。我们只需讨论在区间 $[L, R]$ 内是否能够取到这个最大余数 $n-1$。 余数为 $n-1$ 的数在数轴上紧邻某个 $n$ 的倍数（即 $m \cdot n - 1$）。

• 情况一：区间 $[L, R]$ 跨越了至少一个 $n$ 的整倍数 如果在区间 $(L, R]$ 之间存在一个 $n$ 的整倍数 $m \cdot n$，即： $$\lfloor \frac{L}{n} \rfloor < \lfloor \frac{R}{n} \rfloor$$ 那么该整倍数的前一个数 $m \cdot n - 1$ 必定落在区间 $[L, R]$ 内。此时我们取 $k = m \cdot n - 1$，得到的余数为： $$f(k) = (m \cdot n - 1) \bmod n = n - 1$$ 由于 $n-1$ 是模 $n$ 运算能达到的最大理论上限，因此最大余数直接为 $n-1$。

• 情况二：区间 $[L, R]$ 未跨越任何 $n$ 的整倍数 如果区间内没有 $n$ 的倍数，即： $$\lfloor \frac{L}{n} \rfloor = \lfloor \frac{R}{n} \rfloor$$ 这意味着在区间 $[L, R]$ 内，所有数除以 $n$ 的商都相同。此时余数函数 $f(k) = k \bmod n$ 在该区间内是单调递增的。 因此，最大值一定在区间的右端点 $k = R$ 处取得，最大余数为 $R \bmod n$。

3. 数学公式总结

通过上述分析，该问题可以用 $O(1)$ 的数学公式直接求解： $$\text{Ans} = \begin{cases} n - 1 & \text{若 } \lfloor \frac{L}{n} \rfloor < \lfloor \frac{R}{n} \rfloor \\ R \bmod n & \text{若 } \lfloor \frac{L}{n} \rfloor = \lfloor \frac{R}{n} \rfloor \end{cases}$$

四、 C++11 代码实现

基于上述数学抽象，这两道题的代码实现非常精简高效：

1. 拿苹果 (C++11)

#include <iostream>

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

    int n;
    if (std::cin >> n) {
        int day = 0;       // 总天数 T
        int ans_day = 0;   // 最后一个苹果被拿走的天数 D

        while (n > 0) {
            day++;
            // 如果当前剩余苹果数模 3 余 1，且之前还没记录过最后一个苹果被拿走的天数
            if (ans_day == 0 && n % 3 == 1) {
                ans_day = day;
            }
            // 递减剩余苹果数
            n -= (n + 2) / 3;
        }

        std::cout << day << " " << ans_day << "\n";
    }
    return 0;
}

2. 分糖果 (C++11)

#include <iostream>

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

    int n, l, r;
    if (std::cin >> n >> l >> r) {
        // 利用整数除法判断是否跨越了 n 的整倍数
        if (l / n < r / n) {
            std::cout << n - 1 << "\n";
        } else {
            std::cout << r % n << "\n";
        }
    }
    return 0;
}

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com