首页 > 代码库 > CERC 2013 Magical GCD
CERC 2013 Magical GCD
题目大意如下：给定一个序列，每个序列有值xi,现给定t个数列,对于每个长n的数列，求一段[l,r]使 [r-l+1]*gcd(l,r)最大，gcd(l,r)指的是该连续区间的最大公约数。
不难想到n^3,n^2logx,n^2的暴力吧
n^3DP，n^2logx暴力枚举，n^2DP
可以这样考虑，每次我对于某一个数，保存若干个值，以i为右端点的区间且gcd为某一值的时候这个区间最大的左端点位置是哪里？
但是你也许会认为这样做状态会不会有点多？更新是不是n方的呢？
其实不是的，因为我们可以从左到右来递推。
什么意思呢？对于每一个数，它与前面构成的gcd一定不会太多（约数肯定不会太多），所以我们最多也只需要保存每一个约数为gcd的时候左边最远能够拓展的位置。
其实远远不要保存每一个约数的位置，因为实际上很多的约数都不是gcd，这样我们就可以由左边的所有状态和右边的一个gcd一次来递推了。
当然，我们也可以直接利用指针的自动排序特性（类似链式前向星），我们碰到一个比当前(r-l+1)*val要小的就更新，因为我们再也尝试不到比它大的了。
{$inline on}const maxn=100100;type edge=^node; node=record next,last:edge; pos,val:int64;end;var head,tail:edge; e:array [0..maxn] of edge; n,cnt:longint; ans:int64; f:array [0..maxn] of int64;procedure addedge(pos,value:int64); inline; var p:edge;begin inc(cnt); new(p); p^.next:=head^.next; p^.last:=head; p^.next^.last:=p; p^.last^.next:=p; p^.pos:=pos; p^.val:=value; e[cnt]:=p;end;procedure delete(var p:edge); inline;begin p^.last^.next:=p^.next; p^.next^.last:=p^.last;end;procedure init; inline;begin ans:=0; cnt:=0; head^.val:=0; tail^.val:=0; head^.next:=tail; tail^.last:=head; head^.last:=nil; tail^.next:=nil;end;function gcd(a,b:int64):int64; inline;begin if a mod b=0 then exit(b) else exit(gcd(b,a mod b));end;function max(x,y:int64):int64; inline;begin if x>y then exit(x) else exit(y);end;procedure main;var t,value:int64; i:longint; p:edge;begin read(t); new(head); new(tail); while t<>0 do begin dec(t); init; read(n); ans:=0; for i:=1 to n do begin read(value); addedge(i,value); p:=head^.next; while p<>tail do begin p^.val:=gcd(p^.val,value); ans:=max(ans,p^.val*(i-p^.pos+1)); if p^.val=p^.last^.val then delete(p^.last); p:=p^.next; end; end; writeln(ans); end;end;begin main;end.
CERC 2013 Magical GCD
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。