# CF1139D Steps to One 题解【莫比乌斯反演】【DP】【枚举】

## 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 PQ$ 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

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

## Output

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

## Examples

input

1


output

1


input

2


output

2


input

4


output

333333338


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

## 题解

$$f[i]=1+\frac{\sum_{j=1}^m f[\gcd(i,j)]}m$$

$$f[i]=1+\frac{\sum_{d|i}f[d]\times F(d)}n,x=i$$

$$F(n)=\sum_{i=1}^m[\gcd(x,i)=n]$$

\begin{aligned} G(n)&=\sum_{n|d}F(d)\\ &=\sum_{n|d}\sum_{i=1}^m[\gcd(x,i)=d]\\ &=\sum_{i=1}^m[n|\gcd(x,i)]\\ ?&=\sum_{i=1}^{\left\lfloor\frac mn\right\rfloor}\left[1|\gcd\left(\frac xn,i\right)\right] \end{aligned}

\begin{aligned} G(n)&=\sum_{i=1}^{\left\lfloor\frac mn\right\rfloor}\left[1|\gcd\left(\frac xn,i\right)\right][n|x]\\ &=\left\lfloor\frac mn\right\rfloor\cdot[n|x] \end{aligned}

\begin{aligned} F(n)&=\sum_{n|d}\mu\left(\frac dn\right)G(d)\\ &=\sum_{i=1}^{\left\lfloor\frac mn\right\rfloor}\mu(i)G(ni)\\ &=\sum_{i=1}^{\left\lfloor\frac mn\right\rfloor}\mu(i)\left\lfloor\frac{m}{ni}\right\rfloor[(ni)|x] \end{aligned}

$$F(n)=\sum_{i|\frac xn}\mu(i)\left\lfloor\frac{m}{ni}\right\rfloor$$

\begin{aligned} f[i]&=1+\frac{\sum_{d|i,d<i}f[d]\times F(d)+f[i]\times F(i)}n,x=i\\ \frac{n-F(i)}{n}\cdot f[i]&=1+\frac{\sum_{d|i,d<i}f[d]\times F(d)}n,x=i\\ f[i]&=\frac{n+\sum_{d|i,d<i}f[d]\times F(d)}{n-F(i)},x=i \end{aligned}

## Code：

#include<cstdio>
#include<cstring>
#include<vector>
#define ll long long
#define p 1000000007
using std::vector;
vector<int> v[100100];//约数用 vector 存一下，每次 √m 枚举不是很稳
ll qpow(ll x,ll y)
{
ll ans=1;
while(y)
{
if(y&1)
ans=ans*x%p;
x=x*x%p;
y>>=1;
}
return ans;
}
bool is[100100];
int pri[100100],mu[100100],cnt=0;
ll f[100100];
int n;
int calc(int x,int y)//1~n 中 gcd(x,i)=y 的数的个数
{
int g=x/y,ans=0;
for(int i=0;i<v[g].size();++i)
ans+=mu[v[g][i]]*(n/v[g][i]/y);
return ans;
}
int main()
{
scanf("%d",&n);
f[1]=1;
mu[1]=1;
for(int i=2;i<=n;++i)
{
if(!is[i])
{
pri[++cnt]=i;
mu[i]=-1;
}
for(int j=1;j<=cnt&&i*pri[j]<=n;++j)
{
is[i*pri[j]]=1;
if(i%pri[j])
mu[i*pri[j]]=-mu[i];
else
{
mu[i*pri[j]]=0;
break;
}
}
}
for(int i=1;i<=n;++i)
for(int j=i;j<=n;j+=i)
v[j].push_back(i);
ll ans=1,inv=qpow(n,p-2);
for(int i=2;i<=n;++i)
{
for(int j=0;j<v[i].size()-1;++j)
f[i]=(f[i]+calc(i,v[i][j])*f[v[i][j]]%p)%p;
f[i]=(f[i]*inv+1)%p;
ll g=n-calc(i,i);
f[i]=f[i]*n%p*qpow(g,p-2)%p;
ans=(ans+f[i])%p;
}
printf("%lld\n",ans*qpow(n,p-2)%p);
return 0;
}


### 3 说点什么

0 Followers

Most reacted comment
3 Comment authors
Recent comment authors
Subscribe

sro 反演大师 wjyyy orz

CYJian

orz wjyyy太强了

/* */