AtCoder ARC #122 (東京海上日動 プログラミングコンテスト2021) : E - Increasing LCMs

解法は割とすんなり思いつけたのだが、実装にバグを作りこんでしんどかった。
https://atcoder.jp/contests/arc122/tasks/arc122_e

問題

N要素の整数列Aが与えられる。
この数列を並べ替えた数列Xを考える。
以下を満たすXが作れるか。

• 数列Bを、B[i]=LCM(X[0]...X[i])として作る。Bが狭義単調増加となる

解法

後ろから作ることを考える。
今、A[i]がXの末尾に持っていける条件を考える。
A[i]を除いた全要素のLCMと、A[i]のGCDがA[i]より小さければよい。
よって条件を満たすA[i]を求め、そのたびにXの後ろから埋めて行こう。

「A[i]を除いた全要素のLCM」を愚直に持つと多倍長整数が必要となり面倒だが、LCMを求める過程で適宜A[i]とのGCDを取ればよい。

int N;

__int128 gcd(__int128 x, __int128 y) {
    while (y > 0) {
        __int128 r = x % y;
        x = y;
        y = r;
    }
    return x;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	vector<ll> A(N);
	FOR(i,N) cin>>A[i];
	
	vector<ll> R;
	while(A.size()>1) {
		
		FOR(i,A.size()) {
			__int128 LC=1;
			FOR(j,A.size()) if(i!=j) {
				LC=LC/gcd(LC,(__int128)A[j])*A[j];
				LC=gcd(LC,(__int128)A[i]);
			}
			if(LC!=A[i]) break;
		}
		
		if(i==A.size()) {
			cout<<"No"<<endl;
			return;
		}
		R.push_back(A[i]);
		A.erase(A.begin()+i);
		
	}
	
	R.push_back(A[0]);
	
	cout<<"Yes"<<endl;
	reverse(ALL(R));
	FORR(r,R) cout<<r<<" ";
	cout<<endl;
	
}

まとめ

この変なミスさえなければなぁ。