You have an array a of n non-negative integers Lets define fax=a1modxa2modx…anmodx for some positive integer x Find the biggest x such that fax is a palindromeHere amodx is the remainder of the intege

题意简述

给定一个长度为 $n$ 的非负整数数组 $a$，定义 $f(a,x) = [a_1 \bmod x, a_2 \bmod x, \ldots, a_n \bmod x]$，求最大的 $x$，使得 $f(a,x)$ 是回文序列。

回文序列的定义：对于长度为 $n$ 的数组 $a$，如果 $\forall i \in [1,n]$，有 $a_i = a_{n-i+1}$，则数组 $a$ 是回文序列。

输入格式

第一行一个整数 $t$，表示测试用例的数量。

接下来 $t$ 行，每行格式如下：

第一行一个整数 $n$，表示数组 $a$ 的长度。

第二行 $n$ 个整数 $a_1, a_2, \ldots, a_n$，表示数组 $a$ 的元素。

输出格式

对于每个测试用例输出一行一个整数，表示最大的 $x$，使得 $f(a,x)$ 是回文序列。如果 $x$ 可以取到无穷大，则输出 $0$。

输入样例

4 2 1 2 8 3 0 1 2 0 3 2 1 1 0 3 100 1 1000000000

输出样例

1 2 0 999999900

算法

(暴力枚举) $O(nt^2\sqrt{a_{max}})$

如果 $x$ 非常大的话，我们可以考虑 $x$ 在什么情况下可以取到无穷大。

如果对于任意的 $x$，$f(a,x)$ 都不是回文序列，那么 $x$ 可以取到无穷大。

反之，如果存在某个 $x$，使得 $f(a,x)$ 是回文序列，那么对于所有 $x' \ge x$，$f(a,x')$ 一定也是回文序列。

我们考虑暴力枚举 $x$，枚举的上界可以设为 $\sqrt{a_{max}}$。然后对于每个 $x$，计算出 $f(a,x)$，判断是否是回文序列即可。

时间复杂度

总共有 $nt$ 个测试用例，对于每个测试用例，需要枚举至多 $\sqrt{a_{max}}$ 个 $x$，需要花费 $O(n)$ 的时间计算 $f(a,x)$，判断是否是回文序列需要花费 $O(n)$ 的时间，因此时间复杂度是 $O(nt^2\sqrt{a_{max}})$。

空间复杂度

空间复杂度是 $O(n)$。

Python 代码

时间复杂度：$O(nt^2\sqrt{a_{max}})$