Find the Biggest Palindrome Modulo X

题意简述

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

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

输入格式

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

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

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

第二行 'n' 个整数 'a_1, a_2, ..., 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√a_{max})'

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

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

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

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

时间复杂度

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

空间复杂度

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

Python 代码

时间复杂度：'O(nt^2√a_{max})'。

def is_palindrome(arr):
    n = len(arr)
    for i in range(n // 2):
        if arr[i] != arr[n - i - 1]:
            return False
    return True

t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    max_x = 0
    a_max = max(a)
    for x in range(1, int(a_max ** 0.5) + 1):
        f = [a[i] % x for i in range(n)]
        if is_palindrome(f):
            max_x = x
    if max_x == 0:
        print(0)
    else:
        print(max_x)