1300*B. Big Vova（最大公约数&贪心）

Problem - 1407B - Codeforces

 

解析：

        显然最大的数肯定放到第一个，然后对于之后每一个数，贪心考虑让其最大公约数最大即可。

        时间复杂度log(n^2logn) 

#include
using namespace std;
#define int long long
const int N=2e5+5;
int n,a[N],vis[N];
int gcd(int a,int b){
	return b?gcd(b,a%b):a;
}
void solve(){
	scanf("%lld",&n);
	memset(vis,0,sizeof vis);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
	}
	sort(a+1,a+n+1);
	printf("%lld ",a[n]);
	int p=a[n];
	for(int i=1;i
		int mx,id=-1;
		for(int j=1;j
			if(!vis[j]&&(id==-1||gcd(a[j],p)>mx)){
				id=j;
				mx=gcd(a[j],p);
			}
		}
		printf("%lld ",a[id]);
		vis[id]=1;
		p=gcd(p,a[id]);
	}
	printf("\n");
}
signed main(){
	int t=1;
	scanf("%lld",&t);
	while(t--) solve();
	return 0;
}