Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 148 Solved: 70
给出一个长度在 100 000 以内的正整数序列,大小不超过 10^12。
求一个连续子序列,使得在所有的连续子序列中,它们的GCD值乘以它们的长度最大。
1 5 30 60 20 20 20
80
题解:我会说这题暴力就水过了?= =实际上此题应该采用的方法也差不多就是暴力= =
很明显,当我们从后往前一路求最大公约数时,最多不会超过logN种(HansBug:因为要么就不变,要变就得至少少一半^_^),所以只需要记录下哪些地方可能引起公因数变化即可——
具体方法:求出两两相邻的两数的最大公约数,然后将所有的前一个公因数不是后一个的倍数的位置记录下来,后面专门留意这些位置即可(HansBug:很明显,要是前者是后者的倍数的话,那么既然都是后面的因数,则必然是前面的因数,不可能引起变化,所以记录下这些就够了,之所以不直接把原数列这么干是因为事实证明两两求下之后的数列突然变得异常优美,想想为什么^_^)
还有个萌萌哒优化:当当前的最大公因数即使到数列最前面都难以超越当前最大值的话,就可以跳掉了
(如上是对比,上面的无优化的,下面的是优化的,事实证明快了不是一点= =)
1 /**************************************************************
2 Problem: 4052
3 User: HansBug
4 Language: Pascal
5 Result: Accepted
6 Time:1644 ms
7 Memory:2180 kb
8 ****************************************************************/
9
10 var
11 i,j,k,l,m,n,t:longint;
12 ans,v:int64;
13 a,b:array[0..100005] of int64;
14 c:array[0..100005] of longint;
15 function gcd(x,y:int64):int64;inline;
16 var z:int64;
17 begin
18 while y<>0 do
19 begin
20 z:=x mod y;
21 x:=y;
22 y:=z;
23 end;
24 exit(x);
25 end;
26 begin
27 readln(t);
28 while t>0 do
29 begin
30 readln(n);ans:=0;m:=1;c[1]:=1;
31 for i:=1 to n do
32 begin
33 read(a[i]);
34 if a[i]>ans then ans:=a[i];
35 end;
36 readln;
37 for i:=1 to n-1 do b[i]:=gcd(a[i],a[i+1]);
38 for i:=1 to n-2 do
39 if (b[i] mod b[i+1])<>0 then
40 begin
41 inc(m);c[m]:=i+1;
42 end;
43 c[m+1]:=maxlongint;c[0]:=-1;
44 l:=0;
45 for i:=1 to n-1 do
46 begin
47 while c[l]<=i do inc(l);
48 dec(l);v:=b[i];
49 for j:=l downto 1 do
50 begin
51 if int64(int64(i-c[j]+2)*v)>ans then ans:=(int64(i-c[j]+2)*v);
52 v:=gcd(v,b[c[j]-1]);
53 if int64(int64(i+1)*v)<=ans then break;
54 if v=1 then
55 begin
56 if (i+1)>ans then ans:=i+1;
57 break;
58 end;
59 end;
60 end;
61 writeln(ans);
62 dec(t);
63 end;
64 readln;
65 end.