Codeforces

Luogu

分析

$$
\begin{aligned}
E(X)&=\sum_{i\geq 1} P(X=i)\times i\\
&=\sum_{i\geq 1}P(X\geq i)\\
&=1+\sum_{i\geq 1}P(X>i)\\
&=1+\sum_{i\geq 1}(1-P(\gcd(a_1,a_2,\cdots,a_i)=1))\\
&=1+\sum_{i\geq 1}\frac{m^i-\sum_{d\geq 1}\mu(d)\left\lfloor\frac{m}{d}\right\rfloor^i}{m^i}\\
&=1+\sum_{i\geq 1}\frac{m^i-m^i-\sum_{d\geq 2}\mu(d)\left\lfloor\frac{m}{d}\right\rfloor^i}{m^i}\\
&=1-\sum_{d\geq 2}\mu(d)\sum_{i\geq 1}\left(\frac{\left\lfloor\frac{m}{d}\right\rfloor}{m}\right)^i\\
&=1-\sum_{d\geq 2}\mu(d)\frac{\left\lfloor\frac{m}{d}\right\rfloor}{m-\left\lfloor\frac{m}{d}\right\rfloor}
\end{aligned}
$$

直接算即可。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;
const int mod=1e9+7;
int qpow(int a,int b) { int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
    return c;
}

int p[N],v[N],cnt=0,mu[N];
void sieve(int n) {
    mu[1]=1;
    for (int i=2;i<=n;++i) {
        if (!v[i]) p[++cnt]=i,mu[i]=-1;
        for (int j=1;j<=cnt&&i*p[j]<=n;++j) {
            v[i*p[j]]=1;
            if (i%p[j]) mu[i*p[j]]=-mu[i];
            else break;
        }
    }
}

int main() {
    int m=read(); sieve(m);
    int ans=0;
    for (int i=2;i<=m;++i) 
        ans=(ans+1ll*mu[i]*(m/i)%mod*qpow(m-m/i,mod-2))%mod;
    ans=(1-ans+mod)%mod;
    printf("%d\n",ans);
    return 0;
}