Processing math: 100%

CF-1139

Posted on | Edited on | In | Views:

D. Steps to One

题意

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

题解1

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

f[n]=1+m∑i=1f[gcd(i,n)]mm∑i=1f[gcd(i,n)]=∑d|nf[d]m∑i=1e[gcd(i,n)==d]m∑i=1e[gcd(i,n)==d]=⌊md⌋∑i=1ϵ[gcd(i,nd)]=⌊md⌋∑i=1∑t|gcd(i,nd)μ(t)=∑t|ndμ(t)⌊mdt⌋接下来把右边f[n]的项提出来(m−⌊mn⌋)f[n]=m+∑d|n,d≠nf[d]∑t|ndμ(t)⌊mdt⌋ans=1+m∑i=1f[i]m

题解2

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

k=⌊mn⌋E[n|i]=∞∑j=1j∗kjmj=km1−km=km−kans=1+E[i>1]=1+m∑j=2−μ(j)E[j|i]

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
//解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