题解：CF2085E Serval and Modulo

· · 题解

题目传送门

洛谷

CF

解题思路

我们考虑先分别给数组 a 和数组 b 排个序，此时分两种情况讨论：

时间复杂度 O(n \sqrt{\sum_{i=1}^{n} a_i - b_i} \log n)。

此时有人就会说了：啊，同学，你这个不是 10^{10} 级别的吗，不会 T 飞吗？

但其实从 1 到 10^{10} 中的数的最多因子个数也就 1344 个，不信你问 deepseek，那我们就可以把 \sqrt{\sum_{i=1}^{n} a_i - b_i} 最多当作 1344 就行了，于是我们就可以轻松过掉这题了。

AC Code

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

int n, a[10001], b[10001], c[10001];

bool check(int k) {
    for (int i = 1; i <= n; i++)
        c[i] = a[i] % k;
    sort(c + 1, c + n + 1);
    for (int i = 1; i <= n; i++)
        if (b[i] != c[i])
            return 0;
    return 1;
}

int main() {
    int t;
    scanf("%d", &t);
    for (; t--; ) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        for (int i = 1; i <= n; i++)
            scanf("%d", &b[i]);
        sort(a + 1, a + n + 1);
        sort(b + 1, b + n + 1);
        long long sum = 0;
        bool ok = 1;
        for (int i = 1; i <= n; i++) {
            sum += a[i] - b[i];
            if (a[i] != b[i])
                ok = 0;
        }
        if (ok) {
            printf("%d\n", (int)1e9);
            continue;
        }
        ok = 0;
        for (int i = 1; 1LL * i * i <= sum; i++)
            if (!(sum % i)) {
                if (check(i)) {
                    printf("%d\n", i);
                    ok = 1;
                    break;
                }
                if (i * i != sum) {
                    if (check(sum / i)) {
                        printf("%d\n", sum / i);
                        ok = 1;
                        break;
                    }
                }
            }
        if (!ok)
            printf("-1\n");
    }
}

提交记录。

说句闲话

这题真的有蓝吗？