时间限制: 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\n",ans);return 0;
}