【最大公约数&链表】权值 @upcexam5921

时间限制: 1 Sec 内存限制: 512 MB
题目描述
给定一个长为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

有这样一个性质：
长度为n的序列，子序列gcd的取值最多有logn种
枚举右端点，维护一个不同gcd取值的链表，每次向右枚举一个端点时，反向更新链表，最后维护答案

#define FILE() freopen("../../in.txt","r",stdin)
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
ll a[maxn],b[maxn],s[maxn],ans;
int n,head=0;
int lef[maxn],rig[maxn];//lef[i],rig[i]分别表示i的上一个结点和下一个结点

struct node{//每个结点中存左端点下标和对应左端点到右端点的gcd的值
    ll ind,val;
}nd[maxn];

void link(int l,int r){//链接结点l,r；
    rig[l] = r;
    lef[r] = l;
}

void addnode(int _ind,int _val){//向链表中添加结点
    nd[_ind].ind = _ind;
    nd[_ind].val = _val;
    link(head,_ind);
    head = _ind;
}

void erasenode(int i){//删除结点
    if(head==i){
        head = lef[i];
    }else link(lef[i],rig[i]);
}

ll gcd(ll a,ll b) {
    return !b?a:gcd(b,a%b);
}

int main() {
//    FILE();
    scanf("%d",&n);
    for(int i=1; i<=n; i++) scanf("%lld",a+i);
    for(int i=1; i<=n; i++) {
        addnode(i,a[i]);
        for(int j = lef[head];j;j = lef[j]) {//从右往左遍历链表，因为序列中的数越多，gcd越小
            nd[j].val = gcd(nd[j].val,nd[rig[j]].val);//更新
            if(nd[j].val==nd[rig[j]].val) {//去重
                erasenode(rig[j]);
            }
        }
        for(int j=head; j; j=lef[j]) ans = max(ans,nd[j].val*(i-nd[j].ind+1));//维护答案
    }
    printf("%lld
",ans);
    return 0;
}