[蓝桥杯 2022 国 C] 取模

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

如果 n mod 1..m 没有重复，那么它们只能依次是 0,1,2,...,m-1，等价于 1..m 全都整除 n+1。

OJ: luogu

题目 ID: P8807

难度:普及/提高-

标签:数学数论思维

日期: 2026-06-20 06:22

目录

  1. 题意
  2. 思路
    1. 反过来想：什么时候不会重复
    2. 最后怎么判
  3. 代码
  4. 复杂度
  5. 总结

题意

对每组 n, m，判断是否存在两个不同的数 x < y <= m，满足：

  • n mod x = n mod y

有就输出 Yes，否则输出 No。

思路

先看一个最直接的小数据暴力：

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

using i64 = long long;

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

    int T;
    cin >> T;

    while (T--) {
        i64 n, m;
        cin >> n >> m;

        bool ok = false;
        for (i64 x = 1; x <= m; x++) {
            for (i64 y = x + 1; y <= m; y++) {
                if (n % x == n % y) {
                    ok = true;
                }
            }
        }

        if (ok) {
            cout << "Yes\n";
        }
        else {
            cout << "No\n";
        }
    }

    return 0;
}

暴力版直接枚举 1..m 里所有二元组 (x, y)，检查余数是否相等。
它只能处理很小的 m，但很适合对拍。

反过来想：什么时候不会重复

设 f(i) = n mod i。

如果 f(1), f(2), ..., f(m) 全都不同，那么注意：

  • f(i) < i

于是前 i 个余数一共是 i 个互不相同的数，而且它们都落在区间 [0, i - 1] 里。
这就逼着它们只能正好是：

  • 0, 1, 2, ..., i - 1

再结合 f(1) = 0，可以递推出：

  • n mod i = i - 1

也就是：

  • n + 1 能被 i 整除

所以“没有重复余数”等价于：

  • 1, 2, ..., m 全都整除 n + 1

这又等价于：

  • lcm(1, 2, ..., m) | (n + 1)

最后怎么判

于是答案非常直接：

  • 如果 lcm(1..m) 能整除 n + 1，说明所有余数都不同，输出 No
  • 否则一定有重复，输出 Yes

因为 n <= 1e9，而 lcm(1..m) 增长非常快，实际上只要预处理到超过 1e9 + 1 就够了。

代码

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

using i64 = long long;

const i64 LIMIT = 1000000001LL;

vector<i64> lcm_prefix;

i64 gcd_i64(i64 a, i64 b) {
    while (b != 0) {
        i64 t = a % b;
        a = b;
        b = t;
    }
    return a;
}

void init_lcm() {
    lcm_prefix.push_back(1); // 占位，让下标从 1 开始更顺手

    i64 cur = 1;
    for (int i = 1; ; i++) {
        i64 g = gcd_i64(cur, i);
        i64 nxt = cur / g;
        if (nxt > LIMIT / i) {
            break;
        }
        nxt *= i;
        if (nxt > LIMIT) {
            break;
        }
        lcm_prefix.push_back(nxt);
        cur = nxt;
    }
}

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

    init_lcm();

    int T;
    cin >> T;

    while (T--) {
        i64 n, m;
        cin >> n >> m;

        i64 need = n + 1;

        if (m >= (int) lcm_prefix.size()) {
            cout << "Yes\n";
            continue;
        }

        if (need % lcm_prefix[m] == 0) {
            cout << "No\n";
        }
        else {
            cout << "Yes\n";
        }
    }

    return 0;
}

复杂度

预处理一小段前缀 lcm 之后，每组询问只做一次取模判断：

  • 时间复杂度 O(1)O(1)
  • 空间复杂度 O(1)O(1)

总结

这题真正有用的不是直接找一对 (x, y)，而是先描述“完全没有重复”时会发生什么。

一旦推出：

  • n mod i = i - 1

后面就自然转成了 lcm(1..m) 的整除判断。