P3209 - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: pols_agyi_pols
Tester: kingmessi
Editorialist: iceknight1093

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

There are N players, numbered 1 to N.
The score of player i is \gcd(i, N).

Find an ordering of the players such that:

  • A player with higher score always appears before one with lower score.
  • Between players with the same score, the one with a smaller label comes first.

EXPLANATION:

This is pretty much just a straightforward implementation task.
Here’s one way of doing it.

First, note that \gcd(i, N) will always be an integer between 1 and N.
So, let’s create N lists L_1, L_2, \ldots, L_N.
The list L_g will hold a list of all the people i such that \gcd(i, N) = g, sorted in ascending order.

The lists can be populated as follows:

  • Start with all the lists being empty.
  • Then, for each i = 1, 2, \ldots, N in order:
    • Compute g = \gcd(i, N).
      This can be done either using a loop, or with your language’s inbuilt gcd function.
    • Then, append i to the back of L_g.

Once this is done, we are ready to compute the necessary order.
Let A be an empty array (that will eventually hold the answer).
We do the following:

  • Iterate over g from N down to 1.
  • When processing g, simply append all the elements of L_g to A in order.

In the end, the array A will hold the order we want, so print it.

TIME COMPLEXITY:

\mathcal{O}(N\log N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    ids = [ [] for i in range(n+1) ]
    
    import math
    for i in range(1, n+1):
        ids[math.gcd(i, n)].append(i)
    ans = []
    for i in reversed(range(1, n+1)):
        ans.extend(ids[i])
    print(*ans)