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} = { 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.

Auto comment: topic has been updated by Lucas97 (previous revision, new revision, compare).Auto comment: topic has been updated by Lucas97 (previous revision, new revision, compare).Dude, why so many spaces after return 0 in your implementation? XD

Hahaha, Hi Erik! Well, I really don't know, maybe it was because of the template. Who knows?