### Lucas97's blog

By Lucas97, history, 8 years ago,

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 (pi, pj) = 1 is equal to (i and j don't share any prime factor) iff (pi and pj 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 Gq be the group of all numbers between 1 and n which are divisible by q. In addition, we will keep a group G1 = { 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 px and py will be in some group Gr for any numbers x and y in Gq (r depends on x and y, obviously). However, we could show that p(Gq) = Gr for any prime number q. The proof consists on noticing that if pq belongs to some group Gr then (f(r) , q) is not 1(because r and pq are in the same group) then f(r) belongs to Gq. Now, if y belongs to Gq then (y, x) is not 1 and then (py, r),so py belongs to Gr. Then, p(Gq) Gr. Analogously, we can prove that f(Gr) Gq 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 px = 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 px = 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 (pi, pj) = 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 px(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 px(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(Gq) = Gr, so it is necessary that (number of elements of Gr) = (number of elements of Gq). Then, in the implementation, we will compute (number of elements of every group Gs) 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 px = 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 Gq should be equal to the number of elements of Gr(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 Gq is Gq, 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 Gq are those Gr 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 px could be y or py 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 px and py 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 Gi 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.

• +50

 » 8 years ago, # |   0 Auto comment: topic has been updated by Lucas97 (previous revision, new revision, compare).
 » 8 years ago, # |   0 Auto comment: topic has been updated by Lucas97 (previous revision, new revision, compare).
 » 7 years ago, # |   +26 Dude, why so many spaces after return 0 in your implementation? XD
•  » » 7 years ago, # ^ |   0 Hahaha, Hi Erik! Well, I really don't know, maybe it was because of the template. Who knows?