← 返回题目列表

AtCoder · waipc_qual_a

A. 为所有人提供 Mod

中文机器翻译题面 查看原题

配点 : 500 点

問題文

长度 小于或等于 N 的非负整数序列 A=(A_1,A_2,\ldots,A_N) 会被给予。 这里,2 \leq N 和 A_1 < A_2 < \cdots < A_N 可以得到保证。

您现在将执行以下操作: 执行 1 进行不少于次数。

  • 正整数 x 选择。然后,用所有 i (1 \leq i \leq N), 第A_i 的值为A_i 该值应乘以 x 对除后的余数替换。

此处,操作序列的分数定义为在操作中使用的 x 的最小值。

你的目标是A 使所有元素相等的状态。 求达到目标的操作序列可能的最大分数。

1 对于每一个输入,T 解决案例。

制約

  • 1 \leq T \leq 125000
  • 2 \leq N \leq 250000
  • 0 \leq A_1 < A_2 < \cdots < A_N \leq 10^9
  • T 遍历各个案例 N 的总和为 250000 以下
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

T
case_1
case_2
\vdots
case_T

每个测试用例以以下形式给出。

N
A_1 A_2 \ldots A_N

出力

对每个测试用例输出答案。


入力例 1

4
3
2 3 5
4
4 10 15 25
5
0 10 20 30 40
15
52633263 109965057 177443516 242738411 319866698 372592710 429724665 485840965 570195620 653861052 725414602 781977517 835165877 912632268 988630679

出力例 1

2
6
10
57331794

例如, 当分解为1 在下一个测试用例中,可以按如下方式操作。

  • x=5 执行操作作为。A 是 您也可以写 (2,3,0) 。
  • x=3 执行操作作为。A 是 您也可以写 (2,0,0) 。
  • x=2 执行操作作为。A 是 您也可以写 (0,0,0) 。