[CERC2013] Magical GCD

题面翻译

有 $T$ 组询问，每次给出 $n$ 个数 $a_i$。

你需要找到这个数组的一个子序列（要求编号连续），使得该序列中所有数的最大公约数和序列长度的乘积最大，并输出这个最大值。

题目描述

The Magical GCD of a nonempty sequence of positive integers is defined as the product of its length and the greatest common divisor of all its elements.

Given a sequence $(a_1, \ldots , a_ n)$, find the largest possible Magical GCD of its connected subsequences.

输入格式

The first line of input contains the number of test cases $T(1 \leq T \leq 10000)$. The descriptions of the test cases follow:

The description of each test case starts with a line containing a single integer $n$,( $1 \leq n \leq 100\, 000$). The next line contains the sequence $a_1, a_2 , \ldots , a _ n$, ($1 \leq a_ i \leq 10^{12}$).

第一行一个整数 T（T<=10000），表示有 T 个测试样例。

接下来 T 个测试样例，对于每个测试样例，第一行一个整数 n，第二行 n 个整数，每两个整数之间用空格隔开。

输出格式

For each test case output one line containing a single integer: the largest Magical GCD of a connected subsequence of the input sequence.

对于每个测试样例，输出一行一个整数。

样例 #1

样例输入 #1

1
5
30 60 20 20 20

样例输出 #1

80

提示

原题8000ms时间限制，1G空间限制

本题测试数据较小，限制为3000ms，256M

Time limit: 8000 ms, Memory limit: 1048576 kB.

Central Europe Regional Contest (CERC) 2013

严格测试可以去P7009 [CERC2013] Magical GCD - 洛谷提交