题解：P2436 钦定

· · 题解

题解：P2436 钦定

纯暴力就能过的水题。

1. 解题思路

一眼望过去，不就是取模的运算吗？我们可以枚举循环的周期 k，然后去计算神犇中对 k 取模中最大的，计算蒟蒻中对 k 取模最小的。这里为了方便，我们把取模的余数设定为 1 至 k。

令神犇中对 k 取模中最大的为 p，蒟蒻中对 k 取模最小的为 q，则需要判断 p 与 q 的关系是否符合条件，及判断 p 是否小于 q。如果搜到了一个符合要求的 p 和 q，我们为了满足循环的周期为 k，再把 q 设置成 k-p。最后我们再枚举循环周期时发现一个可以的 p 和 q 就与一个 pair<int, int> 类型的答案去最小值即可。

可以用 pair<int, int> 是因为这个类型重载的小于号是先比较 first，再比较 second，刚好符合题目的要求。

2. 代码实现

就知道你们想要这个，专门删掉了注释。

#include <bits/stdc++.h>
using namespace std;
#define int long long
constexpr int maxn = 1010;
constexpr int inf = 0x7fffffff;
int n, m, a[maxn], b[maxn];
signed main(signed argc, char* argv[]) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    while (cin >> n >> m) {
        pair<int, int> ans = {inf, inf};
        for (int i = 1; i <= n; i++) cin >> a[i];
        for (int i = 1; i <= m; i++) cin >> b[i];
        int x = inf, y = inf;
        bool flg = false;
        for (int i = 1; i <= (n + m) * 10; i++) {
            int xx = -inf, yy = inf;
            for (int j = 1; j <= n; j++) xx = max(xx, a[j] % i ? a[j] % i : i);
            for (int j = 1; j <= m; j++) yy = min(yy, b[j] % i ? b[j] % i : i);
            if (xx >= yy) continue;
            flg = true;
            yy = i - xx;
            ans = min(ans, {xx, yy});
        }
        if (!flg) cout << "NO\n";
        else cout << ans.first << " " << ans.second << "\n";
    }
    return 0;
}

在题解的最后，提前祝大家新年快乐！