Hi guys, given that the tutorial didn't include any solution for problem F of that round, I decided to explain my solution because I'm sure the problem was really interesting.

First step

Let's denote f as the inverse map of p.

We can easily notice that the key is about looking at the prime factors of the numbers because the condition (i, j) = 1 iff (p_i, p_j) = 1 is equal to (i and j don't share any prime factor) iff (p_i and p_j don't share any prime factor). So, we will divide the numbers into some groups(which are not necessarily disjoint) such that any two numbers in the same group share a common prime factor. Then, let G_q be the group of all numbers between 1 and n which are divisible by q. In addition, we will keep a group G₁ = { 1 }, because as we know 1 is coprime with any number and it also doesn't have any prime factor.

Now, these groups are interesting because p_x and p_y will be in some group G_r for any numbers x and y in G_q (r depends on x and y, obviously). However, we could show that p(G_q) = G_r for any prime number q. The proof consists on noticing that if p_q belongs to some group G_r then (f(r) , q) is not 1(because r and p_q are in the same group) then f(r) belongs to G_q. Now, if y belongs to G_q then (y, x) is not 1 and then (p_y, r),so p_y belongs to G_r. Then, p(G_q) G_r. Analogously, we can prove that f(G_r) G_q and that completes the proof.(We used that q is prime, but this proof also works if q = 1).

So, we have proved that any q is mapped into some other r(where q and r are the indexes of the groups i.e. primes or 1). And this is basically all the solution because the next step will be about proving that if h is a bijective map which takes indexes into indexes of groups, then p_x = y is a feasible permutation , where all the prime factors of y are the images by h of the prime factors of x(here we are considering that the only factor of 1 is 1).

Second step

Claim: The only feasible permutations are those which satisfies p_x = y where all the prime factor of y are the images by h of the prime factors of x.

It is fairly easy to prove that if p satisfies the condition stated before, then p satisfies (i , j) = 1 iff (p_i, p_j) = 1

Now, we will prove that the condition is necessary. It is clear that h needs to be bijective(a group can only be mapped into one group).If q is any prime factor of x then h(q) is a prime factor of p_x(because of First Step). If r is any prime factor of y then the preimage of r is a prime factor of the preimage of p_x(This is also the first step, but considering the inverse of h instead of h). (Again, the proof remains true for the case q = 1).

Conclusion

In summary, we have proved that any bijective map h and any permutation satisfying Claim will turn out to be a feasible solution for p. So, the answer will be (#of feasible h)(# number of feasible p given h)

For one hand, number of feasible h is the number of ways to assign a prime r to any other prime q(here we will say 1 is "prime"), but those h are not only random bijective maps between primes, we should remember that the assignment satisfies that h(q) = r iff p(G_q) = G_r, so it is necessary that (number of elements of G_r) = (number of elements of G_q). Then, in the implementation, we will compute (number of elements of every group G_s) which is 1 if s = 1 and n/s if s is a prime greater than 1.(Think about it for a while if it's not clear at the beginning). Then, we should know how many groups have a fixed numbers of elements , say there are gr[t] groups which have t elements. Provided of this notation, the number of maps h will be .( Note that above we were considering the array p was empty, so if p has some entries already assigned, say p_x = y, then we should look at the prime factors of x (in increasing order) and the prime factors of y(in increasing order), here we observe that the i-th prime factor of x assigns(by h) the i-th prime factor of y. So, we observe that x and y should have the same number of prime factors, the number of elements of G_q should be equal to the number of elements of G_r(q and r are the i-th prime factors of x and y) and the assigment(by h) must be injective(then bijective because the sets are finite and have the same number of elementes), otherwise the answer = 0.(The primes must be ordered because if q is less or equal than then the only group with the same numbers of G_q is G_q, and if q is greater than then q is the last prime in the list of x and the groups with the same number of G_q are those G_r where r is a prime greater than , which is also the last one). Then, if ans is not 0, we should reduce gr[t] the number of times that a group with t elements is assigned to other group with t elements. Thus, the right answer for the number of maps h is ans1 =

For the other hand, once we have fixed a feasible h (i.e. assigns primes into primes with the same number of elements in their groups, Claim states that if x and z have the same prime factors, then p_x could be y or p_y could be y(there's no difference). So, we can divide numbers [1,n] into groups with the same factors(for example, {2,4,8} and {6,12,18,24} will be some groups). Again, let's denote by rep[t] the elements which have the same factors of t.(here we could store all the elements of a group in t were t is square-free i.e. the product of the common factors). The answer for the number of feasible permutations p is . (Here we don't have to deal with the verification in which some values of p are already assigned because we already did the verification before(assigment bettwen indexes) i.e. if x and y have the same prime factors, then p_x and p_y have the same prime factors(because of Claim) and we already know that p is bijective).Therefore, we just need to know how many numbers in a collection in which all share the same prime factors are already assigned and decrease rep[t] by one every time we find a number already assigned(p[x] != 0 where x and t have the same prime factors). Thus, in the general case the right answer will be ans2 equals to

Then, The final answer will be ans1 * ans2. It is clear (from the expression of the answer) that the complexity of the algorithm is O(n).

My implementaion ( I have to say that the names of my arrays are different from those that I described here, but I believe that you won't have any problem with these details).

Finally, I will describe Test case #17. Input: 5 0 2 0 4 0 Output: 6

So, here our groups G_i are {1}, {2,4}, {3}, {5}(we were lucky because the groups are disjoint). Then, gr[1] = 3, gr[2] = 1, rep[1] = 1, rep[2] = 2, rep[3] = 1, rep[5] = 1. Given that p[2] = 2, p[4] = 4, then ans1 = 3! * (1 — 1)! = 6, ans2 = 1! * (2 — 2)! * 1! * 1! = 1. Then, ans1 * ans2 = 6.

I hope you understand everything.Please, tell me, if you have any doubt about the solution(I tried to be a bit formal), comment and I will reply as soon as I can.