CF582A(GCDTable贪心)

已知一个序列&＃xff0c;两两gcd得到一张表 &＃xff08;图为4,3,6,2)
现在给出表中所有项&＃xff08;不按顺序&＃xff09;&＃xff0c;给出原序列一个合法解

预处理&＃xff0c;把gcd表存为i的倍数在表中出现hi次&＃xff0c;显然hi是完全平方数&＃xff0c;取根号得到序列中i的倍数出现几次
贪心取最大的那个&＃xff0c;把它从gcd表中删去&＃xff0c;再取..

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define For(i,n) for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)
#define Fork(i,k,n) for(int i&＃61;k;i<&＃61;n;i&＃43;&＃43;)
#define Rep(i,n) for(int i&＃61;0;i
#define ForD(i,n) for(int i&＃61;n;i;i--)
#define RepD(i,n) for(int i&＃61;n;i>&＃61;0;i--)
#define Forp(x) for(int p&＃61;pre[x];p;p&＃61;next[p])
#define Forpiter(x) for(int &p&＃61;iter[x];p;p&＃61;next[p])
#define Lson (x<<1)
#define Rson ((x<<1)&＃43;1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define F (100000007)
#define MAXN (250000&＃43;10)
typedef long long ll;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a&＃43;b)%F;}
ll sub(ll a,ll b){return (a-b&＃43;llabs(a-b)/F*F&＃43;F)%F;}
void upd(ll &a,ll b){a&＃61;(a%F&＃43;b%F)%F;}
int n,a[MAXN];
map<int,int> h;
map<int,int>::iterator it;
int ans[MAXN]&＃61;{0},siz&＃61;0;
void ad(int x)
{it&＃61;h.find(x);if (it!&＃61;h.end()) it->second&＃43;&＃43;;else h[x]&＃61;1;
}int main()
{freopen("data.in","r",stdin);
// freopen(".out","w",stdout);cin>>n;For(i,n*n) scanf("%d",&a[i]);bool flag&＃61;0;For(i,n*n-1){if (a[i]!&＃61;a[i&＃43;1]) {flag&＃61;1;break;}}if (!flag) {For(i,n-1) printf("%d ",a[i]);printf("%d\n",a[n]);return 0;}sort(a&＃43;1,a&＃43;1&＃43;n*n);h.clear();For(i,n*n){for(int x&＃61;1;x*x<&＃61;a[i];&＃43;&＃43;x){if (a[i]%x&＃61;&＃61;0) {ad(x);if (x*xfor(it&＃61;h.begin();it!&＃61;h.end();it&＃43;&＃43;) {int p&＃61;it->first,s&＃61;it->second;h[p]&＃61;sqrt(h[p]);} it&＃61;h.end();it--;while(1){int p&＃61;it->first,s&＃61;it->second;
// cout<ans[&＃43;&＃43;siz]&＃61;p;if (siz&＃61;&＃61;n) break;for(int x&＃61;1;x*x<&＃61;p;&＃43;&＃43;x){if (p%x&＃61;&＃61;0) {h[x]--;if (x*xwhile (it->second&＃61;&＃61;0) it--;}For(i,siz-1) printf("%d ",ans[i]); printf("%d\n",ans[siz]);return 0;
}