ARC122E

标签：ARC122E gcd int ll lcm fo

ARC122E

题目大意：
重排序列 \(\{a_i\}\) ，使前缀 \(\operatorname{lcm}\) 递增。

限制最紧的一定是最后一个数，因此从后往前放数。
考虑如何判断一个数是否能作为结尾。
显然有

\[\gcd \left(\operatorname{lcm}_{j \not = i} \{a_j\} , a_i \right) <a_i \]

但是显然处理不了这么大的数。
容易发现将 \(\gcd\) 放到 \(\operatorname{lcm}\) 里面是一样的效果，这样就只用考虑 \(a_i\) 的因子了，运算中的数一定不会超过 \(a_i\) 。

#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fd(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
typedef long long ll;
const int N=110;
int n;
ll a[N],b[N];
bool bz[N];
int main(){
	scanf("%d",&n);
	fo(i,1,n)scanf("%lld",&a[i]);
	fd(i,n,1){
		int t=0;
		fo(j,1,n)if(!bz[j]){
			ll v=1;
			fo(k,1,n)if(!bz[k] && k!=j){
				ll u=__gcd(a[j],a[k]);
				v=v/__gcd(u,v)*u;
			}
			if(v<a[j]){t=j;break;}
		}
		if(!t){
			puts("No");
			return 0;
		}
		b[i]=a[t];
		bz[t]=1;
	}
	puts("Yes");
	fo(i,1,n)printf("%lld ",b[i]);
	printf("\n");

	return 0;
}

标签：ARC122E,gcd,int,ll,lcm,fo
From： https://www.cnblogs.com/Kelvin2005/p/16894051.html