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

Question

D. GCD Sort
time limit per test1 second
memory limit per test256 megabytes
You are given a permutation p
of integers from 1
to n
. In one operation, you can select two indices i
and j
(1≤i,j≤n)
such that gcd(pi,pj)=1
and swap the elements at those indices. Here, gcd(x,y)
denotes the greatest common divisor of x
and y
.

You need to sort the permutation p
into ascending order using at most 2⋅n
operations. Print the number of operations and the sequence of swaps needed to sort the permutation.

Input
The first line contains an integer t
(1≤t≤104)
— the number of test cases.

For each test case, the first line contains an integer n
(1≤n≤105)
— the length of the permutation and the second line contains n
integers p1,p2,…,pn
— a permutation of integers from 1
to n
.

It is guaranteed that the sum of n
over all test cases does not exceed 3⋅105
.

Output
For each test case, in the first line, print an integer x
(0≤x≤2⋅n)
, the number of operations performed. Then, print x
lines, each containing two integers i
and j
(1≤i,j≤n)
, which indicates a swap between the i
-th and j
-th elements of p
.

If there are multiple ways to achieve the result, print any valid sequence of operations. It can be shown that a solution always exists under the given constraints. Note that you do not have to minimize the number of operations.

Example
InputCopy
5
5
3 1 2 5 4
3
3 2 1
6
6 2 5 1 3 4
4
1 2 3 4
7
5 2 4 3 1 6 7
OutputCopy
3
4 5
1 2
2 3
3
2 3
1 3
1 2
7
3 5
1 4
4 5
3 6
6 4
5 6
3 4
0
2
1 5
3 4
Note
In the third test case,

Initial permutation: [6,2,5,1,3,4]
Swap p3
and p5
: [6,2,3,1,5,4]
Swap p1
and p4
: [1,2,3,6,5,4]
Swap p4
and p5
: [1,2,3,5,6,4]
Swap p3
and p6
: [1,2,4,5,6,3]
Swap p6
and p4
: [1,2,4,3,6,5]
Swap p5
and p6
: [1,2,4,3,5,6]
Swap p3
and p4
: [1,2,3,4,5,6]
So we sorted the permutation using 7
swaps which is under the limit of 2⋅n=2⋅6=12
swaps.

In the fourth test case, the permutation is already sorted so no swaps are needed.

C++ code

Answer 1

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$ $i = 2 \dots n$ :
1. If element $i$ is already in place, do nothing.
2. Otherwise let pos be the current index of $i$ $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.

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

प्रश्न

विचार

Understanding the problem

Clarifying the GCD Sort Algorithm

उत्तर

Idea

Correctness sketch

Complexity

इस प्रश्नोत्तर को साझा करें