有N个数，分别为 b0,b2......,bn−1 现在我们获得了 ∑n−1i=0 ∑n−1j=0a[i∗n+j]=gcd(b[i],b[j]) 这n* n个数，现在把这n* n个数打乱，要求出b数组的n个数，并且从大到小输出
先弱弱的吐槽一句，我比赛的时候忘记把调试时候开成超小的范围（把范围开到1-6了QAQ）改回来了但是还是拿了70( ⊙ o ⊙ )？？感觉数据有点弱 言归正传，在比赛时考虑到最大的数肯定不是其他两个数的gcd，而是自己和自己的gcd，所以最大的一个数肯定是在b数组里面的嘛，次大的数也是同样的道理，到了第三个数，虽然很大可能这个数也是b数组里面的，但是也有可能是最大和次大的数的gcd，到了这个时候方法就很明显了，每次我们取一个当前还在A数组里面最大的数，把它和当前在答案数组中的数都求一遍gcd，并且存在hash里面，在后面如果遇到了一个这样的数，直接把与前面的数的gcd有关的部分去掉，如果去掉后还有剩余，那么就可以把这个数放到答案数组里面了，然后重复上述的步骤，注意一个数在答案数组中可能连续出现多次，所以我们要解一个方程，先把前面的数gcd的部分减掉，设答案数组中为当前数x的倍数有t个，而当前在A数组中剩下的x还有p个，答案中将会出现c个x，那么显然， (c+t)∗(c+t−1)+c=p ，于是我们可以解出c
就在上面啊QwQ
其实很多地方都没有用上，没有看起来这么长(╯‵□′)╯
var i,j,k,l,n,x,t,eu,pp:longint; a,ans:array[0..1000005]of longint; q,p,next:array[0..40005]of longint; bz:array[0..40005]of boolean; procedure qsort(l,r:longint); var i,j,mid:longint; begin i:=l; j:=r; mid:=a[(i+j) div 2]; repeat while a[i]>mid do inc(i); while a[j]<mid do dec(j); if i<=j then begin a[0]:=a[i]; a[i]:=a[j]; a[j]:=a[0]; inc(i); dec(j); end; until i>j; if i<r then qsort(i,r); if l<j then qsort(l,j); end; {procedure makesu; var i,j:longint; begin for i:=2 to eu do if su[i]=false then begin j:=i+i; while j<=eu do begin su[j]:=true; j:=j+i; end; end; end;} procedure work(x,y:longint); var i,j:longint; begin i:=a[next[eu]]; while i>0 do begin if x mod i=0 then inc(p[i],y); i:=a[next[i]]; end; end; function gcd(x,y:longint):longint; begin if y=0 then exit(x) else exit(gcd(y,x mod y)); end; procedure init; begin readln(n); for i:=1 to n*n do read(a[i]); readln; qsort(1,n*n); a[0]:=0; for i:=1 to n*n do if a[i]<eu then break; for j:=i+1 to n*n do if a[j]<>a[j-1] then next[a[j-1]]:=j; i:=1; while a[i]>=eu do begin for j:=i+1 to n*n+1 do if a[j]<>a[i] then break; l:=0; for pp:=ans[0] downto 1 do if ans[pp] mod a[i]=0 then inc(l); if l>=1 then begin i:=j; continue; end; k:=trunc(sqrt(j-i)); work(a[i],k); i:=j; for j:=1 to k do ans[ans[0]+j]:=a[i-1]; ans[0]:=ans[0]+k; if ans[0]>1000 then exit; end; inc(q[a[i]]); inc(i); next[eu]:=i-1; for j:=i to n*n do inc(q[a[j]]); end; begin // assign(input,'1'); reset(input); eu:=trunc(sqrt(1000000000)); //makesu; init; for i:=eu downto 1 do if q[i]-p[i]>0 then begin for j:=1 to n do begin if (p[i]+j)*(p[i]+j-1)+j=q[i] then begin work(i,j); for k:=1 to j do ans[ans[0]+k]:=i; ans[0]:=ans[0]+k; break; end; end; end; for i:=1 to n do write(ans[i],' '); writeln; // close(input); end.