Hi guys, given that the tutorial didn't include any solution for [problem F](http://mirror.codeforces.com/contest/698/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 tow 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$) $\subseteq$ $G_r$. Analogously, we can prove that f($G_r$) $\subseteq$ $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 $\prod\limits_{t = 1}^ngr[t]!$.( 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 $\sqrt[]n$ then the only group with the same numbers of $G_q$ is $G_q$, and if q is greater than $\sqrt[]n$ 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 $\sqrt[]n$, 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 = $\prod\limits_{t = 1}^n(gr[t] - \text{groups with t elements already assigned})!$↵
↵
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 $\prod\limits_{\text{t isfree-squarsquare-free}}rep[t]!$. (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 $\prod\limits_{\text{t is free-squarsquare-free}}(rep[t] - \text{number of x such that p[x] != 0, x and t have the same prime factors})!$↵
↵
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](http://mirror.codeforces.com/contest/698/submission/19956067) ( 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.↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
### 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 tow 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$) $\subseteq$ $G_r$. Analogously, we can prove that f($G_r$) $\subseteq$ $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 $\prod\limits_{t = 1}^ngr[t]!$.( 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 $\sqrt[]n$ then the only group with the same numbers of $G_q$ is $G_q$, and if q is greater than $\sqrt[]n$ 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 $\sqrt[]n$, 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 = $\prod\limits_{t = 1}^n(gr[t] - \text{groups with t elements already assigned})!$↵
↵
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 $\prod\limits_{\text{t is
↵
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](http://mirror.codeforces.com/contest/698/submission/19956067) ( 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.↵
↵
↵
↵
↵
↵
↵
↵
↵
