### PROBLEM LINKS:

### DIFFICULTY

MEDIUM

### EXPLANATION

(Note that it’s well-known that if **N = p _{1}^{k}1 p_{2}^{k2}… p_{m}^{k}m**

_{}, where all pi are distinct primes, then

**φ(N) = p**

_{1}^{k}_{1}-1(p_{1}-1) p_{2}^{k}_{2}^{-1}(p_{2}-1) … p_{m}^{k}_{m}^{-1}(p_{m}-1)).This problem can be solved by fast simulation of the process. For each prime less than 10^{5} (there are 9592 of them) let’s maintain its power which is the actual **power** of this prime in the current value **N _{i}** and its

**delta**which shows how the power will change when we move on to N

_{i}+1. From the formula for

**φ(N)**it can be seen that no delta will change before the set of prime divisors of N

_{i}(without repetitions) changes. That means that there are two types of important events for us:

- one of the prime divisors of
**N**is no longer present in_{i}**N**+1, and_{i} - a prime which is not a divisor of
**N**is now a divisor of_{i}**N**+1._{i}

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 10^{5}). 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**N**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_{i}**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(**m**^{2})). 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 10^{5} (that is, 6) and **P** is the number of primes less than 10^{5} (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 **N _{i}** becomes equal to 1 only when all 2’s in the prime factorization of

**N**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

_{i}**φ**. 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.