Codeforces #46 C Disposition

題意是﹕給出一個1..N的排列，設G = {i: 1 <= i <= N，令存在第j位(1<=j<=N)同時滿足i|j和i|A[j]}，把|G|最小化。

大約觀察所得﹕
1. |G| >= 1。
2. 第i位必不能放i的因子。

猜想﹕
1. 必然存在排列使得|G| = 1。

重要觀察﹕
1. i和i+1必然是互質，即gcd(i, i+1) = 1。
2. 把奇數置於偶數位，把偶數置於奇數位，G = {1}。

故我們可以考慮位置i放i+1，i+1放i，當中i為奇數，並使得只有G={1}。
但需注意若N是奇數的話，第N位只能放N，會使得G={1,N}。但不難發現同樣的方法也適用於i為偶數，因為若第一位放置一，無損G={1}的特質，但可以保証重要觀察的正確性。

故答案如下：

N是奇數：1 3 2 5 4 7 6 9 8 ... N N-1
N是偶數：2 1 4 3 6 5 8 7 ... N N-1