Steps to One
Contest: Codeforces Round 548 (Div. 2)
Difficulty rating: 2300
Tags: dp, math, number theory, probabilities

Vivek initially has an empty array $$$a$$$ and some integer constant $$$m$$$.

He performs the following algorithm:

1. Select a random integer $$$x$$$ uniformly in range from $$$1$$$ to $$$m$$$ and append it to the end of $$$a$$$.
2. Compute the greatest common divisor of integers in $$$a$$$.
3. In case it equals to $$$1$$$, break
4. Otherwise, return to step $$$1$$$.

Find the expected length of $$$a$$$. It can be shown that it can be represented as $$$\frac{P}{Q}$$$ where $$$P$$$ and $$$Q$$$ are coprime integers and $$$Q\neq 0 \pmod{10^9+7}$$$. Print the value of $$$P \cdot Q^{-1} \pmod{10^9+7}$$$.

Input format:
The first and only line contains a single integer $$$m$$$ ($$$1 \leq m \leq 100000$$$).

Output format:
Print a single integer — the expected length of the array $$$a$$$ written as $$$P \cdot Q^{-1} \pmod{10^9+7}$$$.

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

Note:
In the first example, since Vivek can choose only integers from $$$1$$$ to $$$1$$$, he will have $$$a=[1]$$$ after the first append operation, and after that quit the algorithm. Hence the length of $$$a$$$ is always $$$1$$$, so its expected value is $$$1$$$ as well.

In the second example, Vivek each time will append either $$$1$$$ or $$$2$$$, so after finishing the algorithm he will end up having some number of $$$2$$$'s (possibly zero), and a single $$$1$$$ in the end. The expected length of the list is $$$1\cdot \frac{1}{2} + 2\cdot \frac{1}{2^2} + 3\cdot \frac{1}{2^3} + \ldots = 2$$$.

Example input:
1

Example output:
1

Example input:
2

Example output:
2

Editorial:
Let $$$dp[x]$$$ be the expected number of additional steps to get a gcd of 1 if the gcd of the current array is $$$x$$$.
Suppose the current gcd of the array $$$a$$$ is $$$x$$$, after the next iteration of the algorithm, we would append some randomly chosen $$$j$$$ with a probability $$$\frac{1}{m}$$$, and move to state $$$gcd(x,j)$$$ and since the length increases by $$$1$$$ on appending, we will make $$$dp[gcd(x, j)] + 1$$$ steps for this $$$j$$$.
So the recurrence is : $$$$$$ dp[x] =1 + \sum_{j=1}^{m}\frac{dp[gcd(j,x)]}{m} $$$$$$
I recommend this Expectation tutorial to get more understanding of the basics.
We can group together all terms having the same $$$gcd(j, x)$$$, move terms having $$$gcd(j, x) = x$$$ to the left side of the equation and use that to calculate $$$dp[x]$$$.
This is an $$$O(m^2)$$$ solution.
Here we notice that $$$gcd(j,x)$$$ is a factor of $$$x$$$,
So the recurrence could be modified as : $$$$$$ dp[x] = 1+\sum_{y \in divisors(x)}{\frac{dp[y] \cdot f(y,x)}{m}} $$$$$$ where $$$f(y,x)$$$ is the count of integers $$$1 \le p \le m$$$, such that $$$gcd(p,x)=y$$$
Lets express $$$x = y \cdot a$$$, and $$$p=y \cdot b$$$ where $$$a$$$, $$$b$$$ are positive integers,
So we want to find the number of $$$p$$$'s where $$$1 \le p \le m$$$, $$$p = y \cdot b$$$, such that $$$gcd(b,a) = 1$$$, i.e. we want to find number of $$$b$$$ where $$$1 \le b \le m/y$$$ such that $$$gcd(b,a) = 1$$$.
Lets find factorization of $$$a$$$, so $$$b$$$ must not be divisible by any of the prime factors of $$$a$$$.
We can find number of $$$b\le m/y$$$ such that it isn't divisible by some set of primes by inclusion exclusion.
Since there are at most $$$6$$$ primes, we have complexity: $$$O(m \log{m} \cdot 2^6 \cdot 6)$$$
For an alternate solution using mobius function, refer code 2.