寻找最大回文模数 - 算法题解

寻找最大回文模数 - 算法题解/n/n题意简述：/n/n给出一个非负整数序列 a，定义 f(a,x)=[a_1 mod x,a_2 mod x,/dots,a_n mod x]，求最大的 x 使得 f(a,x) 为回文序列，若 x 可以取到无穷大，则输出 0。/n/n思路分析：/n/n1. 取值范围: 因为 x 是除数，所以 x 的取值范围是 [1,max(a_i)]。/n2. 回文判断: 使用双指针，从两端同时向中间扫描，如果有不同的数就不是回文序列。/n3. 最大值枚举: 从大到小枚举 x 的值，如果 f(a,x) 为回文序列，则输出 x，否则继续枚举下一个 x。/n/n如果枚举到 x=1 仍然没有找到合法的 x，则输出 0。/n/n代码实现：/n/npython/ndef find_largest_palindrome_mod(a):/n n = len(a)/n max_a = max(a)/n for x in range(max_a, 0, -1):/n f = [ai % x for ai in a]/n left, right = 0, n - 1/n while left < right:/n if f[left] != f[right]:/n break/n left += 1/n right -= 1/n if left >= right:/n return x/n return 0/n/nt = int(input())/nfor _ in range(t):/n n = int(input())/n a = list(map(int, input().split()))/n print(find_largest_palindrome_mod(a))/n/n/n代码解释：/n/n1. find_largest_palindrome_mod(a) 函数用于求解给定序列 a 的最大回文模数。/n2. 首先获取序列 a 的最大值 max_a，作为枚举范围的起点。/n3. 使用 for 循环从 max_a 到 1 进行枚举。/n4. 对于每个 x，计算 f(a,x)，并使用双指针 left 和 right 判断是否为回文序列。/n5. 如果是回文序列，则返回 x；否则继续枚举。/n6. 如果循环结束仍然没有找到合法的 x，则返回 0。/n/n示例：/n/n/ninputCopy/n4/n2/n1 2/n8/n3 0 1 2 0 3 2 1/n1/n0/n3/n100 1 1000000000/noutputCopy/n1/n2/n0/n999999900/n/n