博客

5921: 权值（GCD，暴力）

  • Post author:
  • Post category:其他


5921: 权值


时间限制:

1 Sec

内存限制:

512 MB


提交:

95

解决:

31

[

提交

][

状态

][

讨论版

][命题人:

admin

]

题目描述


给定一个长为n的正整数序列Ai。对于它的任意一个连续的子序列{Al, Al+1, …, Ar}，


定义其权值W (l, r)为其长度与序列中所有元素的最大公约数的乘积，即W (l, r)  = (r − l + 1) × gcd(Al, Al+1, .., Ar )。



你需要输出权值最大的子序列的权值

输入


第一行一个正整数n。



第二行n个正整数，表示序列Ai。

输出


一行一个正整数，表示答案。

样例输入

5
30 60 20 20 20

样例输出

80

提示

最后四个元素形成的子序列权值最大。

对于前30%的数据：n ≤ 2000

对于所有数据：1 ≤ n ≤ 10

5

,1 ≤ Ai ≤ 10

9

来源


2018山东冬令营

长度为n的子序列中  ， GCD 最多为log(n)

固定右端点(枚举右端点)     去掉重复的 gcd ，  延伸最左端点能达到最长；数组是去重 

#include <bits/stdc++.h>    
typedef long long ll;  
const ll INF=0x3f3f3f3f;  
const int MAXN=1e5+5;  
using namespace std;  
inline ll gcd(ll a,ll b) { return b? gcd(b,a%b):a;}  
    
ll col[MAXN], gc[MAXN], a[MAXN];  
int main()  
{  
    ll ans=-INF;  
    int k=0, n;  
    scanf("%d",&n);  
    for(int i=1;i<=n;i++)  
        scanf("%lld",&a[i]);  
    for(int i=1;i<=n;i++)  
    {  
        col[++k]=i;  
        gc[k]=a[i];  
    
        for(int j=k-1;j>=1;j--)  
            gc[j]=gcd(gc[j],gc[j+1]);  
    
        int cot=0;  
        for(int j=1;j<=k;)  
        {  
            gc[++cot]=gc[j];  
            col[cot]=col[j];  
            while(gc[cot]==gc[j]) j++;  
        }  
        k=cot;  
        for(int j=1;j<=k;j++) 
            ans=max(ans,gc[j]*(i-col[j]+1));  
    }  
    printf("%lld",ans);  
    return 0;  
}  
/**************************************************************
    Problem: 5921
    User: ldu_reserver201701
    Language: C++
    Result: 正确
    Time:128 ms
    Memory:4040 kb
****************************************************************/