2021 分糖果 · 方案二看余数在哪一段

CSP-J 标程 · 复赛真题 · 代码 · cpp · 难度 2/5 · 共 658 字

跨段就是 n-1，同段就是 R 对 n 取余

2021
数学

正文

// CSP-J 2021 复赛 T1 · 分糖果（方案二 · 满分）
// 原题：https://oj.yecheng.tv/p/CSPJ2021A
//
// 方案二 · 看余数在哪一段里（O(1)）
// k mod n 的取值是有规律的：每 n 个数为一个周期，
// 在 [t*n, t*n + n - 1] 这一段里，余数从 0 一路涨到 n - 1。
// 于是只剩两种情况：
//   1. L 和 R 落在同一段里（L / n == R / n）：余数一路递增，最大值就是 R % n；
//   2. 跨过了至少一段的分界：区间里一定含着某一段的末尾，最大值就是 n - 1。
// 复杂度 O(1)。

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

int main() {
    freopen("candy.in", "r", stdin);
    freopen("candy.out", "w", stdout);

    int n, L, R;
    cin >> n >> L >> R;

    if (L / n == R / n) {
        cout << R % n << "\n";      // 同一段内，越靠右余数越大
    } else {
        cout << n - 1 << "\n";      // 跨段，必能取到 n - 1
    }
    return 0;
}

2021 分糖果 · 方案二 看余数在哪一段

正文

CSP-J 标程 · 复赛真题的其它内容

2021 分糖果 · 方案二看余数在哪一段