CF-1139

D. Steps to One

题意

每次从$1\sim m$从等概率的选择一个数, 直到所有选择的数的 gcd 为 1, 问操作的次数的期望是多少?

题解1

设$f[n]$表示当前 gcd 为 n 还需要的步数的期望

$$f[n]=1+\frac {\sum\limits_{i=1}^mf[gcd(i,n)]} m\\ \sum\limits_{i=1}^mf[gcd(i,n)]=\sum\limits_{d|n}f[d]\sum\limits_{i=1}^me[gcd(i,n)==d]\\ \sum\limits_{i=1}^me[gcd(i,n)==d]=\sum\limits_{i=1}^{\lfloor \frac m d\rfloor}\epsilon[gcd(i,\frac n d)] \\=\sum\limits_{i=1}^{\lfloor \frac m d\rfloor}\sum\limits_{t|gcd(i,\frac n d)}\mu(t)=\sum\limits_{t|\frac n d}\mu(t)\lfloor \frac m {dt}\rfloor\\ 接下来把右边f[n]的项提出来\\ (m-\lfloor\frac m n\rfloor)f[n]=m+\sum\limits_{d|n,d\ne n}f[d]\sum\limits_{t|\frac n d}\mu(t)\lfloor \frac m {dt}\rfloor\\ ans=1+\frac {\sum\limits_{i=1}^mf[i]} m$$

题解2

设$E[n|i]$表示 gcd 为 n 的倍数的期望步数

$$k=\lfloor\frac m n\rfloor\\ E[n|i]=\sum\limits_{j=1}^{\infty}j*\frac {k^j} {m^j}=\frac {\frac k m} {1-\frac k m}=\frac k {m-k}\\ ans=1+E[i>1]=1+\sum_{j=2}^m-\mu(j)E[j|i]$$

代码

//解1
int f[N];
int main() {
    int m;
    cin>>m;
    for1(i,m){
        for(int j=1;j*j<=i;j++){
            if(i%j==0){
                if(i/j==j){
                    fac[i].pb(j);
                }else{
                    fac[i].pb(j);
                    fac[i].pb(i/j);
                }
            }
        }
    }
    get_prime();
    f[1]=0;
    ll tot=0;
    forl(n,2,m){
        ll t_tmp=m;
        for0(j,fac[n].size()){
            ll d=fac[n][j];
            if(d==n)continue;
            ll cnt=0;
            for0(k,fac[n/d].size()){
                int t=fac[n/d][k];
                cnt=(cnt+(ll)mu[t]*(m/d/t)%mod)%mod;
            }
            t_tmp=(t_tmp+f[d]*cnt%mod)%mod;
        }
        f[n]=t_tmp*qPow(m-m/n,mod-2,mod)%mod;
        tot=(tot+f[n])%mod;
        // cout<<f[n]<<endl;
    }
    printf("%lld\n",(tot*qPow(m,mod-2,mod)%mod+1)%mod);
    return 0;
}
//解2
bool notPrime[N+1];
int prime[N+1],num_prime=0,mu[N+1];
void get_prime(){
  	notPrime[1]=1;
    for(int i=2;i<=N;i++){
        if(!notPrime[i]) {
            prime[num_prime++]=i;
            mu[i]=1;
        }
        for(int j=0;j<num_prime&&(ll)i*prime[j]<=N;j++){
            int k = i*prime[j];
            notPrime[k] = 1;
            if(i % prime[j] == 0)break;
            else mu[k]=mod-mu[i];
        }
    }
}
ll qpow(ll a,ll b){
    ll ans=1;
    while(b){
        if(b&1)ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
int main() {
#ifdef PerpEternal
    // freopen("/Users/perpeternal/Documents/Sketch/data/in.dat", "r", stdin);
    // freopen("/Users/perpeternal/Documents/Sketch/data/out.dat", "w", stdout);
#endif
    //ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int m;
    in(m);
    get_prime();
    ll ans=1;
    forl(i,2,m){
        ll k=m/i;
        ans=(ans+mu[i]*k%mod*qpow(m-k,mod-2)%mod)%mod;
    }
    printf("%lld\n",ans);
    return 0;
}

引用

https://www.cnblogs.com/zyt1253679098/p/10584706.html
https://blog.csdn.net/neuq_zsmj/article/details/88830388