Codeforces #671 Div2 E. Decryption

遅刻したので本番中に解き切れなかったっぽい。
https://codeforces.com/contest/1419/problem/E

問題

整数Nが与えられる。
Nの約数のうち、1以外のものを任意の順で円環状に並べるとする。
隣接要素が互いに素となるようなケースを極力少なくしたい。

並べ方の一例と、隣接要素が互いに素となる組の最小値を示せ。

解法

Nを素因数分解したとき、素因数の数が1つならどう並べても良い。

2個以上の場合、最初の2つをX,Yとする。
Nの約数dに対し、f(d)をdをX,Yで割り切れるだけ割った値とする。
S(k) := f(d)=kとなるdの集合
とすると、k＞1であればS(k)内の要素は互いにGCDがkの倍数であることが確定する。

よって、k＞1であるS(k)についてはそれぞれ連続するように並べていこう。
その際、S(k)の両端がXかYの倍数であるようにする。
最後S(1)に該当するものを連結しなければならないが、
(Xの倍数), XY, (Yの倍数)と置くことで両端をうまくつなげられる。

int T;
ll N;

map<int,int> enumpr(int n) {
	map<int,int> V;
	for(int i=2;i*i<=n;i++) while(n%i==0) V[i]++,n/=i;
	if(n>1) V[n]++;
	return V;
}

vector<int> enumdiv(int n) {
	vector<int> S;
	for(int i=1;i*i<=n;i++) if(n%i==0) {S.push_back(i); if(i*i!=n) S.push_back(n/i); }
	sort(S.begin(),S.end());
	return S;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		
		map<int,int> M=enumpr(N);
		vector<int> C=enumdiv(N);
		vector<int> V;
		
		if(M.size()==1) {
			V=C;
			V.erase(V.begin());
		}
		else {
			x=M.begin()->first;
			M.erase(M.begin());
			y=M.begin()->first;
			map<int,set<int>> Q;
			FORR(c,C) if(c>1) {
				i=c;
				while(i%x==0) i/=x;
				while(i%y==0) i/=y;
				Q[i].insert(c);
			}
			deque<int> D;
			D.push_back(x*y);
			for(i=x;N%i==0;i*=x) D.push_back(i);
			for(i=y;N%i==0;i*=y) D.push_front(i);
			FORR(d,D) Q[1].erase(d);
			
			
			int pre=1;
			FORR(q,Q) {
				if(q.first!=1) {
					i=D.back();
					D.push_back(i/pre*q.first);
					q.second.erase(D.back());
					i=D.front();
					D.push_front(i/pre*q.first);
					q.second.erase(D.front());
				}
				FORR(v,q.second) D.push_back(v);
				pre=q.first;
			}
			FORR(d,D) V.push_back(d);
			
			
			
		}
		
		
		
		
		int num=0;
		FOR(i,V.size()) if(__gcd(V[i],V[(i+1)%V.size()])==1) num++;
		FORR(v,V) cout<<v<<" ";
		cout<<endl;
		cout<<num<<endl;
		
		
	}
}

まとめ

結構面倒な構築問題。