#4488. [Jsoi2015] 最大公约数

[Jsoi2015] 最大公约数

题目描述

给定一个长度为 N 的正整数序列Ai对于其任意一个连续的子序列 {A_{l},A_{l+1}...A_{r}},我们定义其权值W(L,R )为其长度与序列中所有元素的最大公约数的乘积,即W(L,R) = (R-L+1) ∗ gcd (A_{l}..A_{r})。 JYY 希望找出权值最大的子序列。

输入格式

输入一行包含一个正整数 N。 接下来一行,包含 N个正整数,表示序列Ai 1 < =  Ai < =  10^12, 1 < =  N < =  100,000

输出格式

输出文件包含一行一个正整数,表示权值最大的子序列的权值。

5
30 60 20 20 20

80
//最佳子序列为最后 4 个元素组成的子序列。

提示

没有写明提示

题目来源

没有写明来源