输入格式
第一行一个正整数$n$。
第二行$n$个正整数，表示序列$A_i$。
输出格式
一行一个正整数，表示答案。
样例
样例输入：
5
30 60 20 20 20
样例输出：
80
数据范围与提示
样例解释：
最后四个元素形成的子序列权值最大。
数据范围：
对于前$30\%$的数据：$n\leqslant 2,000$
对于所有数据：
$1\leqslant n\leqslant {10}^5$
$1\leqslant A_i\leqslant {10}^9$
题解
再一次没有打正解……
暴力都会，我们现在考虑剪枝。
$\alpha.$将所有数求一个$gcd$，然后都把它们除这个$gcd$，最后答案记得乘上就好了。
$\beta.$如果以当前的$gcd$进行到序列最后也不能更新答案，那么$break$。
你可能会觉得会被卡成$\Theta(n^2)$，但是仔细分析一下会发现，最劣的情况即为等比数列，而等比数列长度不会长于$、\log \max(A_i)$，所以我们最多会将整个数列扫$\log \max(A_i)$遍。
时间复杂度：$\Theta(n\log \max(A_i)$。
期望得分：$100$分。
实际得分：$100$分。
代码时刻
原文：https://www.cnblogs.com/wzc521/p/11551584.html