给定N个数，每两个数有一个最大公约数，求最大的最大公约数。N<=10^5，每个数<=10^6

枚举求是N^2*logN的，必定超时

换一个思考的角度，如果我们假设最大公约数是多少，用多少时间可以判定是否成立呢？

假设判定x，那么给变量每次加x，看有没有这个值，有的话就计数器加一，计数器一旦大于1，就成立，跳出即可。

这样，我们开一个10^6的数组，v[i]记录值为i的数的个数，判定有没有值时就是O(1)的了，总体时间在max_number*logN左右

1 program sgu499(input,output);  2 var  3    v     : array[0..1100000] of longint;  4    n,max : longint;  5 procedure init;  6 var  7    i,x : longint;  8 begin  9    fillchar(v,sizeof(v),0); 10    max:=0; 11    readln(n); 12    for i:=1 to n do 13    begin 14       readln(x); 15       inc(v[x]); 16       if x>max then 17      max:=x; 18    end; 19 end; {
      init } 20 function check(x :longint ):boolean; 21 var 22    s,sum : longint; 23 begin 24    s:=0; 25    sum:=x; 26    while (sum<=max) do 27    begin 28       s:=s+v[sum]; 29       if s>1 then 30       begin 31      check:=true; 32      exit; 33       end; 34       sum:=sum+x; 35    end; 36    check:=false; 37 end; {
      check } 38 procedure main; 39 var 40    i : longint; 41 begin 42    for i:=max downto 1 do 43       if check(i) then 44       begin 45      writeln(i); 46      break; 47       end; 48 end; {
      main } 49 begin 50    init; 51    main; 52 end.