CAREFUL - Editorial

editorial
, , ,
1

PROBLEM LINKS:

Practice
Contest

DIFFICULTY

MEDIUM

EXPLANATION

(Note that it’s well-known that if N = p1k1 p2k2… pmkm, where all pi are distinct primes, then φ(N) = p1k1-1(p
1-1) p2k2-1(p
2-1) … pmkm-1(p
m-1)).

This problem can be solved by fast simulation of the process. For each prime less than 105 (there are 9592 of them) let’s maintain its power which is the actual power of this prime in the current value Ni and its delta which shows how the power will change when we move on to Ni+1. From the formula for φ(N) it can be seen that no delta will change before the set of prime divisors of Ni (without repetitions) changes. That means that there are two types of important events for us:

  • one of the prime divisors of Ni is no longer present in Ni+1, and
  • a prime which is not a divisor of Ni is now a divisor of Ni+1.
    Now no delta changes between neigboring events. This allows us to process a lot of iterations between neigboring events quickly. It’s easy to find out which of the deltas change during the event and how (if we precalculate the factorizations of positive integers less than 105). To find out which of the events is going to happen next, one may use a data structure called heap.containing one entry for each prime number, where each entry contains the number of iterations with the current set of deltas that will pass before the presence of this prime in the current value Ni changes. The smallest of these numbers should be kept at the top of the heap so that we can quickly find the next event. After changing the corresponding deltas during the event, we shouldn’t forget to change some of the corresponding entries in the heap.

This still requires some speed-up, as we can’t afford changing the powers by the deltas before each event (there are at least m events, so our solution’s running time will become at least O(m2)). Instead, let’s keep another variable lastChange for each prime denoting the index of the last iteration when this prime’s delta changed. Now any prime’s power can be found in O(1) when needed as power + delta * (currentIteration - lastChange) (don’t forget to update power and lastChange after that), and we don’t need to make O(m) additions before each event anymore.

The overall complexity of the solution is thus O**(E(D** + log P)), where E is the number of events, D is the largest number of distinct prime divisors of a number less than 105 (that is, 6) and P is the number of primes less than 105 (that is, 9592). It can also be easily shown that E ? P log P in the worst case (and in fact E is even less).

As the problem tester, Aleksey came up with a simpler solution to this problem. Note that φ(N) is even for N > 2 (as N either contains an odd prime divisor or is a power of 2). This means that Ni becomes equal to 1 only when all 2’s in the prime factorization of Ni disappear, so we may forget about primes other than 2 and only care about the power of 2 in the factorization. Using this observation, the solution becomes really simple. We can precalculate the power of 2 generated by each prime less than 105 by iterations of φ. After that, we can simply add the corresponding powers for all primes given in the input. This number (possibly increased by 1 if initially N is odd) is in fact the answer to the problem.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

1 Like
2

There is a much simpler solution!

To understand the approach, first suppose we could solve the problem with dynamic programming. DP[t][p] represents the frequency of prime p in the t-th step. The transition would be as follows:

While there is at least one prime p_i such that DP[t][p_i] is positive:

   Initialize all values in DP[t+1] with 0
   For each prime p_i such that DP[t][p_i] is positive, do the following:

      DP[t+1][p_i] += DP[t][p_i] - 1

      x = p_i - 1

      For each prime factor p_j of x, do:

         y=amount of times p_j divides x
         DP[t+1][p_j] += y * DP[t][p_i]

   t++

The final value of t will be the answer! This can be found out using the euler-totient formula Gennady already explained in the editorial.

The previous algorithm will obviously not pass in time. But one can notice an interesting property in this process. Any number x = p_i - 1, p_i > 2 and p_i is a prime, will always have 2 as a divisor. Therefore, for all valid t, DP[t][2] will be positive. This means DP[t][2] has to be the last prime whose frequency goes to zero. Therefore, whenever DP[t][2] = 0, the process ends, and t is the answer.

This enables us to solve the problem with the simple following algorithm, where freq[p] is the frequency of prime p:

For w = MAX_PRIME; w is bigger than 2: w--
   if w is a prime:
     x = w - 1
     For each prime factor p_j of x, which appears, do:

         y=amount of times p_j divides x
         freq[p_j] += y * freq[w]

 output freq[2]

We just have to consider the edge case in which freq[2] was 0 initially, in which we only have to do:
output freq[2] + 1

Efficiency:

  • O(nlog(n)) time, O(n) space.

Code:

1 Like