The Holmes Children
Contest: ICM Technex 2017 and Codeforces Round 400 (Div. 1 + Div. 2, combined)
Difficulty rating: 2100
Tags: math, number theory

The Holmes children are fighting over who amongst them is the cleverest.

Mycroft asked Sherlock and Eurus to find value of f(n), where f(1) = 1 and for n ≥ 2, f(n) is the number of distinct ordered positive integer pairs (x, y) that satisfy x + y = n and gcd(x, y) = 1. The integer gcd(a, b) is the greatest common divisor of a and b.

Sherlock said that solving this was child's play and asked Mycroft to instead get the value of $$g(n) = \sum_{d|n} f\left(\frac{n}{d}\right)$$. Summation is done over all positive integers d that divide n.

Eurus was quietly observing all this and finally came up with her problem to astonish both Sherlock and Mycroft.

She defined a k-composite function Fk(n) recursively as follows:

$$$$

She wants them to tell the value of Fk(n) modulo 1000000007.

Input format:
A single line of input contains two space separated integers n (1 ≤ n ≤ 1012) and k (1 ≤ k ≤ 1012) indicating that Eurus asks Sherlock and Mycroft to find the value of Fk(n) modulo 1000000007.

Output format:
Output a single integer — the value of Fk(n) modulo 1000000007.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first case, there are 6 distinct ordered pairs (1, 6), (2, 5), (3, 4), (4, 3), (5, 2) and (6, 1) satisfying x + y = 7 and gcd(x, y) = 1. Hence, f(7) = 6. So, F1(7) = f(g(7)) = f(f(7) + f(1)) = f(6 + 1) = f(7) = 6.

Example input:
7 1

Example output:
6

Example input:
10 2

Example output:
4

Editorial:
Hint: For n = 10, the pairs satisfying the conditions are (1, 9), (3, 7), (7, 3), (9, 1). The first members of each pair form the set {1, 3, 7, 9}. Similarly, for n = 12, the corresponding set is {1, 5, 7, 11}. Also, observe that f(n) = n - 1 whenever n is a prime.
Editorial: Given, $$x+y=N \text{ and } gcd(x,y)=1$$ $$\Rightarrow gcd(x,n-x)=1$$ $$\Rightarrow gcd(x,n)=1$$ $$\implies x \text{ is coprime to } n$$ Now,let's prove the converse. Let x be coprime to n and y = n - x. Let gcd(x, y) = k ≠ 1 $$\Rightarrow k \text{ divides both } x \text{ and } n-x$$ $$\Rightarrow k \text{ divides } n$$ $$\Rightarrow k \text{ divides both } x \text{ and } n \text{ which is a contradiction}$$ $$\Rightarrow gcd(x,y)=1$$ Thus, number of distinct ordered pairs (x,y) satisfying the conditions= φ(n) where φ() denotes Euler totient function.
Now,$$g(n) = \sum_{d|n} \phi\left(\frac{n}{d}\right)$$. Let S denote the set {1, 2, ..., n}. We distribute the integers of S into disjoint sets as follows. For each divisor d of n, let A(d) = {k∈S: gcd(k, n) = d}.The sets A(d) form a disjoint collection whose union is S. Let n(A(d)) denote the number of integers in A(d). If k is a number in A(d), then k = d * m for some m coprime to n / d. There are φ(n / d) such m in the interval [1, n]. Hence, n(A(d)) = φ(n / d). Since the sets A(d) are disjoint, $$\sum_{d|n} n(A(d)) = n$$ $$\Rightarrow \sum_{d|n} \phi(n/d) = n$$ $$\implies g(n) = n$$
So, we only need to consider the number of times we apply f() in Fk which is (k + 1) / 2 for a given k.
Now, let us consider the numbers in the set {1, 2, ..., 2n}. There are exactly n even and n odd numbers in the set. The n even numbers can never be coprime to 2n. So, φ(2n) ≤ n. Thus, we need to calculate φ() at most log(n) times.
Complexity: $${ \mathcal { O } } ( { \sqrt { n } } * \log ( n ) )$$