题解：P2436 钦定

furina_yyds · 2025-01-13 15:34:59 · 题解

勉强够黄题的难度。

思路

这道题有周期，需要使用模。

可以发现，当答案合法时，必然满足 \max (a_i \bmod d) < \max (b_i \bmod d)。

枚举答案，判断是否合法，即可。

注意

多测不清空，爆零两行泪。

代码

#include <iostream>
#include <vector>
#include <limits>
#include <algorithm>

// 函数：计算数组元素对除数取模的最大余数
int maxRemainder(const std::vector<int>& arr, int divisor) {
    int maxRem = 0;
    for (const auto& element : arr) {
        int rem = element % divisor;
        if (rem == 0) {
            rem = divisor;
        }
        maxRem = std::max(maxRem, rem);
    }
    return maxRem;
}

// 函数：计算数组元素对除数取模的最小余数
int minRemainder(const std::vector<int>& arr, int divisor) {
    int minRem = std::numeric_limits<int>::max();
    for (const auto& element : arr) {
        int rem = element % divisor;
        if (rem == 0) {
            rem = divisor;
        }
        minRem = std::min(minRem, rem);
    }
    return minRem;
}

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

    while (true) {
        int n, m;
        std::cin >> n >> m;
        if (std::cin.fail()) {
            break;  // 当输入不合法时终止循环
        }
        std::vector<int> a(n);
        std::vector<int> b(m);

        for (int i = 0; i < n; ++i) {
            std::cin >> a[i];
        }
        for (int i = 0; i < m; ++i) {
            std::cin >> b[i];
        }

        int mina = std::numeric_limits<int>::max();
        int minb = std::numeric_limits<int>::max();

        for (int i = 1; i <= (n + m) * 10 + 1; ++i) {
            int man = maxRemainder(a, i);
            int mim = minRemainder(b, i);

            if (man < mim) {
                if (man < mina) {
                    mina = man;
                    minb = i - man;
                } else if (man == mina && i - man < minb) {
                    minb = i - man;
                }
            }
        }

        if (mina == std::numeric_limits<int>::max() && minb == std::numeric_limits<int>::max()) {
            std::cout << "NO\n";
        } else {
            std::cout << mina << " " << minb << '\n';
        }
    }
    return 0;
}