(Note that it’s well-known that if N = p1k1 p2k2… pmkm, where all pi are distinct primes, then φ(N) = p1k1-1(p
2-1) … pmkm-1(p
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.
Can be found here.
Can be found here.