JZOJ链接 (原题CF583C) 粗略的大意就是给出一个n*n的被打乱的序列A,其中每个A序列中的数都是B序列中两个数的Gcd 即对于任意 Ai ，有 Ai=Gcd(Bj,Bk)(1≤j,k≤N) ,且j,k不重复 求原来的B数组，B是不下降的(可以把它当成输出格式)。 首先我们就要尝试研究Gcd的性质 首先容易想到， Gcd(a,a)=a 因此A序列中有N项是B序列的 而且 Gcd(a,b)≤a,b 因此在A序列之中，B[1]一定是那个最大的数。 于是我们把A序列从大到小排序后，最大的数(A[1])就是B[1] 不难想到A[2]是B[2]，但A[3]一定是B[3]吗？ 不一定，还有可能是Gcd(B[1],B[2])。 所以我们可以想到这样的思路：每当我们把当前A序列中最大的数取出来到B数组时，假设当前是第i个，则在A序列中删掉这个数和前面i-1个数的Gcd，而且因为A数组中有着 Gcd(Bi,Bj) ，也有 Gcd(Bj,Bi) ，所以这个数要删掉两次。 因为 1≤Ai≤109 ，所以我们需要用Hash表（或许离散化也可以）存取记录每个数剩余的数量，排序后扫一遍即可。 算法的最坏复杂度为 O(n2) ，因为 1≤n≤103 ，复杂度可以接受。
代码
var a,h,ct:array[0..10000000] of longint; f:array[0..1000] of longint; n,m,i,j,k,x:longint; procedure qsort(l,r:longint); var i,j,mid,t:longint; begin i:=l; j:=r; mid:=a[(i+j) shr 1]; repeat while a[i]>mid do inc(i); while a[j]<mid do dec(j); if i<=j then begin t:=a[i]; a[i]:=a[j]; a[j]:=t; inc(i); dec(j); end; until i>j; if j>l then qsort(l,j); if i<r then qsort(i,r); end; function hash(x:longint):longint; var i:longint; begin i:=x mod 9100009; while (h[i]<>0)and(h[i]<>x) do i:=(i mod 10000000)+1; h[i]:=x; exit(i); end; function gcd(x,y:longint):longint; begin if x mod y=0 then exit(y) else exit(gcd(y,x mod y)); end; begin assign(input,'data.in');reset(input); assign(output,'data.out');rewrite(output); readln(n); m:=n*n; for i := 1 to m do read(a[i]); qsort(1,m); for i := 1 to m do begin x:=hash(a[i]); inc(ct[x]); end; k:=0; for i := 1 to m do begin x:=hash(a[i]); if ct[x]>0 then begin inc(k); f[k]:=a[i]; dec(ct[x]); for j := 1 to k-1 do begin x:=gcd(f[k],f[j]); dec(ct[hash(x)],2); end; end; if k=n then break; end; for i := 1 to n do write(f[i],' '); close(input);close(output); end.