まず、 \(A\) と \(B\) が多重集合として等しい必要があります。また、 \(\frac{N}{2} < p\) を満たす素数 \(p\) について、 \(A_p\) は動かすことができません。

逆に、ともに上記を満たさない整数の組 \((i,j)\) について、 \(11\) 回以内の操作で \(\mathrm{swap}(A_i,A_j)\) をすることが可能です。

具体的には、以下のようにすればよいです。

\(i,j\) の最小素因数を \(p,q\) として \(i=pa,j=qb\) と分解する。

\(v=(i,p,2p,2,2q,q,j)\) とおく。 \(v\) の要素で等しいものがあったときはその区間を無いものとして、 \(\mathrm{swap}(v_k,v_{k+1})\) を \(k=1,2,\ldots,|v|-1,\ldots,2,1\) の順に行う。

この事実より、 \(i=2,3,\ldots,N\) の順に \(A_i=B_i\) となるように操作していけば \(11N\) 回以下で \(A=B\) とすることができます。

適切に実装することで時間計算量は \(O(N \log N)\) になります。

想定解 (C++)