yukicoder : No.1509 Swap!!

コードが非常に短く済む問題。
https://yukicoder.me/problems/no/1509/editorial

問題

正整数N,A,Bが与えられる。
1～NのPermutationが与えられたとき、要素番号がAまたはB離れた2値をswapすることを任意回数行えるものとする。
この時、入力がどんなPermutationでも昇順にソートできるか判定せよ。

解法

N頂点の無向グラフを考える。
頂点iと(i+A)、頂点iと(i+B)を辺で結んだ時、この無向グラフが連結なら任意の2要素をswapできるので条件を満たす。
まずGCD(A,B)=1は明らかに必須。

頂点iと(i+A)を辺で結んでできるグラフは、min(N,A)個の連結成分からなる。よってあとmin(N,A)-1本以上の辺を張る必要がある。
頂点iと(i+B)を辺で結ぶとき、この辺はN-B本しか張れないので、(min(N,A)-1)≦(N-B)をチェックすればよい。

int T;
ll A,B,N;

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>T;
	while(T--) {
		cin>>N>>A>>B;
		
		if(__gcd(A,B)>1) {
			cout<<"NO"<<endl;
			continue;
		}
		if(A+B<=N+1) {
			cout<<"YES"<<endl;
		}
		else {
			cout<<"NO"<<endl;
		}
		
	}
}

まとめ

こちらはシンプルで良いね。