2.8-05:最大公约数（GCD）(CSP-J/S NOIP NOI)-点码成金编程

Home => ProblemSet => 2.8-05:最大公约数（GCD）

Problem1219--2.8-05:最大公约数（GCD）

Time Limit: 5 Sec Memory Limit: 64 MB Submit: 1 Solved: 1
[ Submit ] [ Status ] [ Creator: ][ 参考程序 ]

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

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

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

5
30 60 20 20 20

最佳子序列为最后 4 个元素组成的子序列
权值最大子序列=区间长度*区间最大公约数

[ Submit ] [ Status ]