Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom10月前

09/11
12:43
单调栈/队列

[bzoj 4488] [Jsoi2015]最大公约数

♦♦♦♦♦♦   Description   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Input   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Output   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Sample Input   ♦♦♦♦♦♦

5
30 60 20 20 20

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

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

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

JSOI原题大赛(雾)

同bzoj4052 维护一个单调栈就可以了

c++:

pascal:

 

[bzoj 4488] [Jsoi2015]最大公约数