5921: 权值
题目描述
给定一个长为n的正整数序列Ai。对于它的任意一个连续的子序列{Al, Al+1, ..., Ar},
定义其权值W (l, r)为其长度与序列中所有元素的最大公约数的乘积,即W (l, r) = (r − l + 1) × gcd(Al, Al+1, .., Ar )。
你需要输出权值最大的子序列的权值
你需要输出权值最大的子序列的权值
输入
第一行一个正整数n。
第二行n个正整数,表示序列Ai。
第二行n个正整数,表示序列Ai。
输出
一行一个正整数,表示答案。
样例输入
5
30 60 20 20 20
样例输出
80
提示
最后四个元素形成的子序列权值最大。
对于前30%的数据:n ≤ 2000
对于所有数据:1 ≤ n ≤ 105,1 ≤ Ai ≤ 109
由这个题知道了一个小知识:n个数里面最多有log(n)个不同的gcd。
所以这道题可以枚举i,先求出i之前所有不同的gcd,再分别与a[i]进行gcd,只保留不同的gcd。
还要记下每个不同gcd开头的位置。
最后遍历一遍gcd找出最大的权值就可以。
#include <bits/stdc++.h> using namespace std; typedef long long ll; struct node{ ll data; ll w; }; ll gcd(ll x,ll y){ return y==0?x:gcd(y,x%y); } int n,m=0; ll a[100005],maxx=-1; node ans[100005]; map<ll,ll> M; int main() { scanf("%d",&n); for(int i=0;i<n;i++) scanf("%lld",&a[i]); for(int i=0;i<n;i++){ int k=0; M.clear(); for(int j=0;j<m;j++){ ll t=gcd(a[i],ans[j].data); if(M[t]==0){//用map判断gcd是否出现过 M[t]++; ans[k].data=t; ans[k].w=ans[j].w; k++; } } if(M[a[i]]==0){//第i个数本身加进gcd里 M[a[i]]++; ans[k].data=a[i]; ans[k].w=i; k++; } m=k; for(int j=0;j<m;j++) if(ans[j].data*(i-ans[j].w+1)>maxx) maxx=ans[j].data*(ll)(i-ans[j].w+1); } printf("%lld\n",maxx); return 0; }