For the first ~20\%~ of the points, we note that when ~n~ is prime, then all ~x~ from ~1~ to ~n-1~ satisfy ~\gcd(n,x) = 1~, so by Bézout's Lemma, there exist ~c,d~ such that ~xc + nd = 1~, or equivalently, ~xc \equiv 1 \pmod{n}~. That is, every non-zero element in ~\mathbb{Z}_n~ is a unit.

We can either simply print all numbers from ~1~ to ~n-1~ as a unit, but code that has a correct unit check, does not check if a unit is irreducible or prime, and does not time out will also pass.

Time Complexity: ~\mathcal{O}(n)~ or ~\mathcal{O}(n^2)~ (unit checking only)

For the next ~20\%~ of the points, we brute force check if elements are units or not in ~\mathcal{O}(n^2)~ time by checking every possible pair of elements. Then, we brute force check if elements are irreducible or not in ~\mathcal{O}(n^3)~ by checking every possible triple of non-units.

To find prime elements, we try every possible combination of ~p,a,b,x,y,z~ to check if ~p~ is prime.

Time Complexity: ~\mathcal{O}(n^6)~

For the next ~20\%~, we note that we do not need to try every possible combination of ~p,a,b,x,y,z~ and instead, we just need to go over every possible ~p,a,b,x~, using booleans to mark when ~px \equiv ab, px \equiv a, px \equiv b \pmod{n}~.

Time Complexity: ~\mathcal{O}(n^4)~

For full points, we precompute whether or not for any pair ~a,b~, there exists ~x~ such that ~ax \equiv b \pmod{n}~. This can be done in ~\mathcal{O}(n^3)~ time. In fact, we say that ~a~ divides ~b~ when this is true.

Then, we only need to go over every possible ~p,a,b~, using the precomputed divisibility array.

Time Complexity: ~\mathcal{O}(n^3)~