## 原始题面

time limit per test: 2 seconds

memory limit per test: 256 megabytes

input: standard input

output: standard output

### Description

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\ne 0\pmod{10^9+7}$$. Print the value of $$P\cdot Q^{-1}\pmod{10^9+7}$$

### Input

The first and only line contains a single integer $$m$$ ($$1\leqslant m\leqslant 100000$$)

### Output

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

### 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^1}+2\cdot\frac{1}{2^2}+3\cdot\frac{1}{2^3}+...=2$$

## 解题思路

$$O(m\log m)$$ 的概率 DP 做法看官方题解即可，这里讲讲 $$1\leqslant m\leqslant 10^{11}, 1\leqslant p\leqslant 10^{12}$$ 时候 (即 第六届团体程序设计天梯赛 的 L3-3) 该怎么做

\begin{aligned} E(X)&=\sum_{i=1}^{\infty}iP(X=i)&(1)\\ &=\sum_{i=1}^{\infty}\sum_{j=1}^iP(X=i)&(2)\\ &=\sum_{i=1}^{\infty}P(X\geqslant i)&(3)\\ &=1+\sum_{i=1}^{\infty}(1-P(X\leqslant i))&(4)\\ &=1+\sum_{i=1}^{\infty}\left(1-P\left(\gcd_{j=1}^ia_i=1\right)\right)&(5)\\ &=1+\sum_{i=1}^{\infty}\left(1-\sum_{d=1}^m\mu(d)\left({\lfloor\frac{m}{d}\rfloor\over m}\right)^i\right)&(6)\\ &=1-\sum_{i=1}^{\infty}\sum_{d=2}^m\mu(d)\left({\lfloor\frac{m}{d}\rfloor\over m}\right)^i&(7)\\ &=1-\sum_{d=2}^m\mu(d)\sum_{i=1}^{\infty}\left({\lfloor\frac{m}{d}\rfloor\over m}\right)^i&(8)\\ &=1-\sum_{d=2}^m\mu(d){\lfloor\frac{m}{d}\rfloor\over m-\lfloor\frac{m}{d}\rfloor}&(9)\\ \end{aligned}

• $$(1)\to (4)$$: 常规操作
• $$(5)$$: 由题意立得
• $$(6)$$: 容斥 / Möbius 反演
• $$(7)$$: 不难注意到 $$d=1$$ 时，$$\mu(d)\left({\lfloor\frac{m}{d}\rfloor\over m}\right)^i=1$$ (结合题意想想为何会这样)
• $$(8)$$: 交换求和号以处理掉级数
• $$(9)$$: 考虑几何级数

u1s1, 这题考察的范围还挺广

• 预先算一遍 $$\sum_{i=1}^m\mu(i)$$, 这样整除分块过程中要求的所有 $$\sum\mu$$ 就都被求过一遍了
• 因为我们往往使用 map$$\sum\mu$$, 所以在整除分块的过程中可以用变量记录上一步的 $$\sum\mu$$

## 复杂度

• 预先筛出 $$\mu(i)$$, $$i=1,2,...,n$$
• $$f(x)=\lfloor\frac{m}{x}\rfloor$$
• 杜教筛求 $$\sum_{i=1}^n\mu(i)$$ 的时间复杂度为 $$\Theta(T(n))$$

$\Theta\left(n+T(n)+\sum_{i\in f([2,m]_{\mathbb{N}})}\log p\right)=O\left(n+\frac{m}{\sqrt n}+\sqrt m\log p\right)$

Show code