题目
题目链接：https://codeforces.com/problemset/problem/1139/D
给一个数列，每次随机选一个 (1) 到 (n) 之间的数加在数列末尾，数列中所有数的 (gcd=1) 时停止，求期望长度。
思路
设 (f[i]) 表示数列 (gcd) 等于 (i) 的时候，期望多少步会让 (gcd=1)。
那么显然可以枚举 (i) 的每一个因子来转移。
[f[i]=1+frac{1}{m}sum_{d|i}f[j] imes g(lfloorfrac{n}{d}
floor,frac{i}{d})
]
其中 (g(i,j)) 表示 (1sim i) 中与 (d) 互质的数的个数。
那么有
[g(i,j)=sum_{d|j}mu(d)lfloorfrac{i}{d}
floor
]
那么可以先将 (i) 的因子扔到一个 vector 中。由于最终每个数 (k) 作为因子会被枚举 (lfloorfrac{n}{k}
floor) 次，所以均摊时间复杂度是 (O(log n)) 的。
转移时发现等号右边也含有 (f[i])，所以拆开扔到左边去
[(frac{n-g(lfloorfrac{n}{i}
floor,1)}{n})f[i]=1+frac{1}{n}sum_{d|i}f[d] imes g(lfloorfrac{n}{d}
floor,frac{i}{d})
]
[f[i]=frac{n+sum_{d|i}f[d] imes g(lfloorfrac{n}{d}
floor,frac{i}{d})}{n} imes frac{n}{n-g(lfloorfrac{n}{i}
floor,1)}
]
[f[i]=frac{n+sum_{d|i}f[d] imes g(lfloorfrac{n}{d}
floor,frac{i}{d})}{n-g(lfloorfrac{n}{i}
floor,1)}
]
然后就可以 (O(nlog^2 n)) 做了。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100010,MOD=1e9+7;
int n,m,mu[N],prm[N];
ll ans,f[N],h[N];
bool v[N];
vector<int> d[N];
void findprm(int n)
{
mu[1]=1;
for (int i=2;i<=n;i++)
{
if (!v[i]) prm[++m]=i,mu[i]=-1;
for (int j=1;j<=m;j++)
{
if (i>n/prm[j]) break;
v[i*prm[j]]=1; mu[i*prm[j]]=-mu[i];
if (i%prm[j]==0)
{
mu[i*prm[j]]=0;
break;
}
}
}
}
ll fpow(ll x,ll k)
{
ll ans=1;
for (;k;k>>=1,x=x*x%MOD)
if (k&1) ans=ans*x%MOD;
return ans;
}
ll calc(ll n,ll m)
{
ll s=0;
for (int i=0;i<d[m].size();i++)
s=(s+mu[d[m][i]]*(n/d[m][i]))%MOD;
return s;
}
int main()
{
findprm(N-10);
scanf("%lld",&n);
for (int i=1;i<=n;i++)
for (int j=i;j<=n;j+=i)
d[j].push_back(i);
f[1]=1; ans=fpow(n,MOD-2);
for (int i=2;i<=n;i++)
{
for (int j=0;j<d[i].size()-1;j++)
f[i]=(f[i]+f[d[i][j]]*calc(n/d[i][j],i/d[i][j]))%MOD;
f[i]=(n+f[i])*fpow(n-calc(n/i,1),MOD-2)%MOD;
ans=(ans+f[i]*fpow(n,MOD-2))%MOD;
}
printf("%lld",ans%MOD);
return 0;
}