Steps to One
初始给一个空的数列，每次随机从 \(\left[1 , m \right]\) 中选一个整数加入数列末尾，求数列 \(\gcd = 1\) 时的期望长度。
这是一个期望加莫反的很有意思的题目。
首先我们定义 \(E(x)\)，它表示数列的第一个数为 \(x\) 的时候数列的期望长度。其中 \(E(1)=1\)。
那么我们的答案就是 \(\sum _ { i = 1 } ^ { m } E ( x )\)。
我们有关于期望的方程：
\[\begin{aligned} E(x) = & 1 + \dfrac{1}{m}\sum _ { i = 1 } ^ { m } E (\gcd ( i , x ) ) \\ = & 1 + \dfrac{1}{m}\sum _ { d= 1}\sum _ { i = 1 } ^ { m } E ( d ) \left[ \gcd( i , x) = d\right] \\ = & 1 + \dfrac{1}{m}\sum _ { d= 1} E ( d ) \sum _ { i = 1 } ^ { \left\lfloor m / d \right\rfloor } \left[ \gcd \left( i , \dfrac{x}{d}\right) = 1\right] \\ = & 1 + \dfrac{1}{m}\sum _ { d= 1} E ( d ) \sum _ { i = 1 } ^ { \left\lfloor m / d \right\rfloor } \sum _ { k \mid i , k \mid x/d} \mu ( k ) \\ = & 1 + \dfrac{1}{m}\sum _ { d= 1} E ( d ) \sum _ { k \mid x/d} \mu ( k ) \left\lfloor \dfrac{m}{kd}\right\rfloor \\ = & 1 + \dfrac{1}{m}\sum _ { T \mid x }\sum _ { d\mid T} E ( d ) \mu \left( \dfrac{T}{d}\right)\left\lfloor \dfrac{m}{T}\right\rfloor \\ = & 1 + \dfrac{1}{m}\sum _ { T \mid x }\sum _ { d\mid T, d \ne x} E ( d ) \mu \left( \dfrac{T}{d}\right)\left\lfloor \dfrac{m}{T}\right\rfloor + \dfrac{\left\lfloor m/x\right\rfloor}{m} E (x) \end{aligned} \]现在对方程移项并变换系数，我们得到了 \(E(x)\) 的递推式：
\[E(x) = \dfrac{m}{ m - \left\lfloor m/x\right\rfloor} + \dfrac{1}{ m - \left\lfloor m/x\right\rfloor}\sum _ { T \mid x }\sum _ { d\mid T, d \ne x} E ( d ) \mu \left( \dfrac{T}{d}\right)\left\lfloor \dfrac{m}{T}\right\rfloor \]这个显然就是 \(O( n \ln n )\) 可处理的了。
代码：
#include<iostream>
#include<cstdio>
#include<vector>
#define ll long long
using namespace std;
namespace Ehnaev{
inline ll read() {
ll ret=0,f=1;char ch=getchar();
while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
return ret*f;
}
inline void write(ll x) {
static char buf[22];static ll len=-1;
if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
else {putchar(10);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
while(len>=0) putchar(buf[len--]);
}
}using Ehnaev::read;using Ehnaev::write;
const ll mo=1e9+7,N=1e5;
ll m,cnt,ans;
ll e[N+5],mu[N+5],f[N+5],prime[N+5];
vector<ll> dv[N+5];
bool ff[N+5];
inline ll Qpow(ll b,ll p) {
ll r=1;while(p) {if(p&1) r=r*b%mo;b=b*b%mo;p>>=1;}return r;
}
inline void Init() {
e[1]=1;ff[1]=1;mu[1]=1;
for(ll i=2;i<=m;i++) {
if(!ff[i]) {prime[++cnt]=i;mu[i]=mo-1;}
for(ll j=1;j<=cnt&&i*prime[j]<=m;j++) {
ff[i*prime[j]]=1;
if(i%prime[j]==0) {
mu[i*prime[j]]=0;break;
}
mu[i*prime[j]]=mu[i]*mu[prime[j]]%mo;
}
}
for(ll i=1;i<=m;i++) {f[i]=(f[i]+mu[i])%mo;}
for(ll i=1;i<=m;i++) {
for(ll j=i;j<=m;j+=i) {
dv[j].push_back(i);
}
}
}
int main() {
m=read();Init();
for(ll i=2;i<=m;i++) {
e[i]=m;ll tmp=0;
for(ll j=0;j<dv[i].size();j++) {
ll t=dv[i][j];
tmp=(tmp+f[t]*(m/t)%mo)%mo;
}
e[i]=(e[i]+tmp)%mo;e[i]=e[i]*Qpow(m-m/i,mo-2)%mo;
for(ll j=i,cn=1;j<=m;j+=i,cn++) {
f[j]=(f[j]+e[i]*mu[cn]%mo)%mo;
}
}
ll invm=Qpow(m,mo-2);
for(ll i=1;i<=m;i++) {ans=(ans+invm*e[i]%mo)%mo;}
write(ans);
return 0;
}