大英网站建设工作,最新联播新闻,制作网页app,网站设计联系电话P9032 [COCI2022-2023#1] Neboderi
题目大意
有一个长度为 n n n的序列 h i h_i hi#xff0c;你需要从中选择一个长度大于等于 k k k的子区间 [ l , r ] [l,r] [l,r]#xff0c;使得 g ( h l h l 1 ⋯ h r ) g\times (h_lh_{l1}\cdotsh_r) g(hlhl1⋯hr)最小你需要从中选择一个长度大于等于 k k k的子区间 [ l , r ] [l,r] [l,r]使得 g × ( h l h l 1 ⋯ h r ) g\times (h_lh_{l1}\cdotsh_r) g×(hlhl1⋯hr)最小其中 g gcd ( h l , h l 1 , … , h r ) g\gcd(h_l,h_{l1},\dots,h_r) ggcd(hl,hl1,…,hr)。 1 ≤ k ≤ n ≤ 1 0 6 , 1 ≤ h i ≤ 1 0 6 1\leq k\leq n\leq 10^6,1\leq h_i\leq 10^6 1≤k≤n≤106,1≤hi≤106 题解
当确定了 l l l时 gcd ( h l , h l 1 , … , h r ) \gcd(h_l,h_{l1},\dots,h_r) gcd(hl,hl1,…,hr)随着 r r r的增大而减小。
每当 gcd \gcd gcd减小时其 gcd \gcd gcd相对于原来的 gcd \gcd gcd肯定有若干个质因数的次数减小。那么对于一个确定的 l l l gcd ( h l , h l 1 , … , h r ) \gcd(h_l,h_{l1},\dots,h_r) gcd(hl,hl1,…,hr)的取值不会超过 log a l \log a_l logal个数。
先用 S T ST ST表维护区间 gcd \gcd gcd。枚举 l l l在二分每一段 g c d gcd gcd值相等的区间并取该区间的右端点作为 r r r来更新答案。
设 v v v为 a i a_i ai的最大值则时间复杂度为 O ( n log n log v ) O(n\log n\log v) O(nlognlogv)。
当然这是跑不满的而且时限为 2.50 s 2.50s 2.50s所以可以过。 code
#includeiostream
#includecstdio
using namespace std;
const int N1000000;
int n,k,now,v[N5],lg[N5],f[N5][20];
long long ans0,sum[N5];
int gcd(int i,int j){while(j){i%j;swap(i,j);}return i;
}
int gt(int l,int r){int xlg[r-l1];return gcd(f[l][x],f[r-(1x)1][x]);
}
int to(int w,int be,int hv){int lbe1,rn,mid;while(lr){midlr1;if(gt(w,mid)hv) lmid1;else rmid-1;}return l-1;
}
int main()
{scanf(%d%d,n,k);lg[0]-1;for(int i1;in;i){lg[i]lg[i/2]1;scanf(%d,v[i]);sum[i]sum[i-1]v[i];f[i][0]v[i];}for(int i1;i19;i){for(int j1;jn-(1i-1);j){f[j][i]gcd(f[j][i-1],f[j(1i-1)][i-1]);}}for(int l1,r;ln-k1;l){nowgt(l,lk-1);rto(l,lk-1,now);while(rn){ansmax(ans,gt(l,r)*(sum[r]-sum[l-1]));if(rn) break;nowgt(l,r1);rto(l,r1,now);}}printf(%lld,ans);return 0;
}
