Minimize Fixed Points

The trap here is thinking we need some clever matching algorithm. We don't. The graph has a very polite number-theory structure, so a simple rotation construction does the whole job.

Forced Fixed Points

First, $1$ is forced.

For every constrained position $i\ge 2$, we need $\gcd(p_i,i)>1$. But $\gcd(1,i)=1$, so value $1$ cannot appear at any position $2,3,\dots,n$. Therefore $p_1=1$ in every valid permutation. Fixed point number one. Rude, but fair.

Now take a prime $q>\frac n2$. At position $q$, the value $p_q$ must share a factor with $q$. Since $q$ is prime, that means $p_q$ must be divisible by $q$. But among $1,2,\dots,n$, the only multiple of $q$ is $q$ itself, because $2q>n$.

So every prime $q>\frac n2$ is also forced to be fixed.

That gives a lower bound:

$$1 + \#\{\text{primes } q : q>n/2\}$$

fixed points. If we can build a permutation with exactly those fixed points, we are done.

How To Move Everything Else

Suppose we have a bunch of numbers that all share some prime factor $q$:

$$a_1,a_2,\dots,a_k$$

If we cyclically rotate their values like

$$p_{a_1}=a_2,\quad p_{a_2}=a_3,\quad \dots,\quad p_{a_k}=a_1,$$

then every position still receives a number divisible by $q$, so every gcd is at least $q$.

Also, if $k\ge 2$, nobody in that group stays fixed. Nice.

So the whole problem becomes: partition all non-forced numbers into groups of size at least $2$, where every group has a common prime factor.

Largest Prime Factor Groups

For each number $x>1$, assign it to the group of its largest prime factor.

Example: $12$ goes to prime $3$, because $12=2^2\cdot 3$. Number $20$ goes to prime $5$.

Now look at a prime $q\le \frac n2$. Its group contains at least:

$$q \quad \text{and} \quad 2q$$

Both are at most $n$, and both have largest prime factor $q$. So this group has size at least $2$, meaning we can rotate it with no fixed points.

What about primes $q>\frac n2$? Their group is just $\{q\}$, exactly the forced fixed case we already proved unavoidable. No magic can save those guys.

Implementation Trick

Instead of explicitly computing largest prime factors, process primes in descending order.

For a prime $q$, collect all multiples of $q$ that have not been used yet. Since larger primes were handled earlier, these are exactly the numbers whose largest prime factor is $q$.

If the collected list has size at least $2$, cyclically rotate it and mark all its numbers used.

If the collected list has size $1$, leave it alone. That only happens for forced large primes.

Initialize $p_i=i$ for all $i$, so untouched forced positions stay fixed automatically.

Correctness Proof

Every assigned group is made of multiples of the same prime $q$. After rotating the group, each index receives another multiple of $q$, so $\gcd(i,p_i)\ge q>1$.

The groups are disjoint because once a number is used, it is never collected again. Rotating each group preserves exactly the same set of values inside that group, and untouched values stay at themselves, so the final array is a permutation.

No rotated group creates a fixed point because every rotated group has size at least $2$.

The only untouched numbers are $1$ and primes greater than $n/2$. We already proved every valid permutation must fix exactly those positions. Therefore our construction has the minimum possible number of fixed points.

Complexity

Sieve primes up to the maximum $n$ once. For each test case, scanning multiples over all primes costs about $O(n\log\log n)$, easily fine for total $n\le 10^5$.