D. GCD Sort time limit per test1 second memory lim...

Below is a simple $O(n)$ algorithm that always sorts the permutation with ≤ 2 n − 1 swaps, well under the required limit of $2n$.

Idea

• Use the element 1 as a “pivot”.
  • gcd(1, x)=1 for every $x$, so any swap that involves the position holding 1 is always allowed.
• Bring 1 to position 1 once (if it is not already there).
• Then, for every position $i=2\dots n$:
  1. If element $i$ is already in place, do nothing.
  2. Otherwise let pos be the current index of $i$.
     • Swap positions pos and 1 – now 1 is at pos, and $i$ is at index 1.
     • Swap positions 1 and $i$ – this puts $i$ in its correct place and returns 1 to index 1.
• Each misplaced element needs at most two swaps, plus perhaps one initial swap to move 1 to the front ⇒ ≤ 2 n − 1 swaps total.

Correctness sketch

• Every swap either:
  • moves the pivot 1 (allowed with anyone), or
  • moves an element $i>1$ together with 1.
    Thus every swap satisfies the gcd=1 rule.
• After processing positions 1…$k$ the prefix is sorted, and 1 is back at position 1.
  Inductively, when we finish position $n$ the entire array is sorted.

Complexity

• Each element is moved at most once (besides the pivot), so time $O(n)$ and memory $O(n)$.

cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;                     // number of test cases
    if (!(cin >> T)) return 0;
    while (T--) {
        int n;
        cin >> n;
        vector<int> p(n + 1);          // 1-based permutation
        vector<int> pos(n + 1);        // pos[val] = index
        for (int i = 1; i <= n; ++i) {
            cin >> p[i];
            pos[p[i]] = i;
        }

        vector<pair<int,int>> ops;     // record swaps (i, j)

        // Step 1: put 1 at index 1 if needed
        if (pos[1] != 1) {
            int idx = pos[1];
            swap(p[1], p[idx]);
            pos[p[idx]] = idx;
            pos[p[1]] = 1;
            ops.emplace_back(1, idx);  // swap indices (1, idx)
        }

        // Step 2: fix each position i = 2 .. n
        for (int i = 2; i <= n; ++i) {
            if (p[i] == i) continue;   // already correct
            int idx = pos[i];          // current position of value i

            // swap idx ↔ 1 (pivot)
            if (idx != 1) {
                swap(p[1], p[idx]);
                pos[p[idx]] = idx;
                pos[p[1]] = 1;
                ops.emplace_back(1, idx);
            }

            // swap 1 ↔ i  (places i correctly)
            swap(p[1], p[i]);
            pos[p[i]] = i;
            pos[p[1]] = 1;
            ops.emplace_back(1, i);
        }

        // Output
        cout << ops.size() << '\n';
        for (auto [a, b] : ops) cout << a << ' ' << b << '\n';
    }
    return 0;
}

The program prints a valid sequence of swaps for every test case, always within the allowed $2n$ operations.