#P4052. [Cerc2013]Magical GCD

    ID: 3254 传统题 3000ms 128MiB 尝试: 775 已通过: 249 难度: 5 上传者: 标签>CF1800普及+/提高-线性 DP消除被支配候选欧几里得算法滚动数组

[Cerc2013]Magical GCD

题目描述

给出一个长度在 10510^5 以内的正整数序列 aa,大小不超过 101210 ^ {12}。

求一个连续子序列,使得在所有的连续子序列中,它们的 gcd⁡\gcd 值乘以它们的长度最大。

输入格式

第一行一个整数 TT 表示有 TT 组数据。

对于每组数据的第一行是一个数 nn ,表示序列长度为 nn。

然后接下来 nn 个整数表示这个序列。

输出格式

对于每组数据输出一行一个整数代表所有连续子序列中,它们的 gcd⁡\gcd 值乘它们的长度的最大值。

1 
5 
30 60 20 20 20
80

数据规模与约定

对于 100%100\% 的数据,1≤n≤1051 \le n \le 10^5,1≤ai≤10121\le a_i \le 10^{12}。