题解：CF2085E Serval and Modulo

题目传送门

解题思路

我们考虑先分别给数组

a

和数组

b

排个序，此时分两种情况讨论：

$a$ 数组和 $b$ 数组一摸一样，这说明取模后和取模前一样，也就是说模数一定大于数组 $a$ 中的所有数，且 $a$ 中的最大值一定小于等于 $10^6$ ，所以直接输出 $10^9$ 一定是对的。
$a$ 数组和 $b$ 数组不一样，那我们看一看取模的本质，对于 $a$ 数组，每个元素对 $k$ 取模后相当于减少了若干个 $k$ 。此时我们对 $a$ 和 $b$ 一一对应的去看，令 $p$ 为 $\sum_{i=1}^{n} a_i - b_i$ ，那么求出这个 $p$ 后， $k$ 一定是 $p$ 的因数，然后我们对于每个 $p$ 的因数暴力的去判断，最后不要忘了无解输出 -1。

时间复杂度

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

CPP

#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");
    }
}

提交记录。

说句闲话

这题真的有蓝吗？

题解：CF2085E Serval and Modulo

文章操作

题目传送门

解题思路

AC Code

说句闲话

相关推荐

评论

题解：CF2085E Serval and Modulo