bzoj2257

不难发现其实这个捣鼓过程就是一个辗转相减
所以最小燃料是瓶容量的最小公约数
然后穷举约数即可

 1 var a:array[0..3000010] of longint;
 2     n,k,x,i,m,j,t:longint;
 3 
 4 procedure sort(l,r: longint);
 5   var i,j,x,y:longint;
 6   begin
 7     i:=l;
 8     j:=r;
 9     x:=a[(l+r) shr 1];
10     repeat
11       while a[i]<x do inc(i);
12       while x<a[j] do dec(j);
13       if not(i>j) then
14       begin
15         y:=a[i];
16         a[i]:=a[j];
17         a[j]:=y;
18         inc(i);
19         j:=j-1;
20       end;
21     until i>j;
22     if l<j then sort(l,j);
23     if i<r then sort(i,r);
24   end;
25 
26 begin
27   readln(n,k);
28   for i:=1 to n do
29   begin
30     readln(x);
31     m:=trunc(sqrt(x));
32     for j:=1 to m do
33       if x mod j=0 then
34       begin
35         inc(t);
36         a[t]:=j;
37         if j*j<>x then
38         begin
39           inc(t);
40           a[t]:=x div j;
41         end;
42       end;
43   end;
44   sort(1,t);
45   m:=1;
46   for i:=t-1 downto 0 do
47   begin
48     if a[i]=a[i+1] then inc(m)
49     else begin
50       if m>=k then
51       begin
52         writeln(a[i+1]);
53         halt;
54       end;
55       m:=1;
56     end;
57   end;
58 end.

View Code