使用C++解决问题：题目描述 你有一个由n个非负数组成的数组a。让我们定义f(a,x)=[a1 mod x,a2 mod x,...,an mod x]，对于某个正整数x，找到最大的x，使f(a,x)是一个回文数组。 这里，a mod x是a除以x的整数的余数。如果一个数组的反向读数与正向读数相同，那么它就是一个回文数组。更确切地说，一个长度为n的数组，如果对每一个i(1≤i≤n)ai=an-i+1，就是一个回文数组。 输入描述 第一行包含一个整数t（1≤t≤105)--测试案例的数量。 每个测试案例的第一行包含一个整数n（1≤n≤105). 每个测试用例的第二行包含n个整数ai（0≤ai≤109). 保证所有n的总和不超过105。 输出描述 对于每个测试案例，输出最大的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

题目描述

有一个长度为 $ n $ 的数组 $ a $，对于一个正整数 $ x $，定义 $ f(a,x)=[a_1 \ \bmod \ x, a_2 \ \bmod \ x, …, a_n \ \bmod \ x]$，其中 $\bmod$ 表示取模。找到最大的正整数 $ x $，使得 $ f(a,x) $ 是一个回文数组。如果 $ x $ 可以无限大，则输出 $ 0 $。

输入格式

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

每个测试用例的第一行包含一个整数 $ n $，表示数组 $ a $ 的长度。

每个测试用例的第二行包含 $ n $ 个整数 $ a_1, a_2, …, a_n $，表示数组 $ a $ 中的元素。

输出格式

对于每个测试用例，输出最大的 $ x $，使得 $ f(a,x) $ 是一个回文数组。如果 $ x $ 可以无限大，则输出 $ 0 $。

数据范围

$ 1 \leq T \leq 10^5 $

$ 1 \leq \sum n \leq 10^5 $

$ 0 \leq a_i \leq 10^9 $

输入样例

4
2
1 2
8
3 0 1 2 0 3 2 1
1
1
4
0 3 2 1

输出样例

1
2
0
999999900

算法1

(二分答案) $O(n\log w)$

首先我们可以发现，$ x $ 取值越大，$ f(a,x) $ 的每个元素的值就越小，因此我们可以考虑使用二分答案来找到最大的 $ x $。

具体来说，我们可以二分 $ x $ 的取值范围 $ [l,r] $，然后对于每个猜测的取值 $ x_{mid} $，计算 $ f(a,x_{mid}) $ 是否是一个回文数组。我们可以使用双指针来判断是否为回文数组，具体来说，我们可以从左右两端同时扫描，如果发现不一致的元素，则说明不是回文数组。

时间复杂度

二分的时间复杂度为 $ O(\log w) $，其中 $ w $ 是元素的最大值。对于每个猜测的取值 $ x_{mid} $，我们需要遍历整个数组，因此总时间复杂度为 $ O(n\log w) $。

C++ 代码