Steps to One
\(CF\) 星不知道多少，开口放不知道 \(T\) 几。
简化题意
给一个数列，每次随机选一个 \(1\) 到 \(m\) 之间的数加在数列末尾，数列中所有数的 \(\gcd = 1\) 时停止，求期望长度。
\(m \le 10 ^ 5\)
题解
久违的推式子题，简单式子（虽然我推了一上午）。
先来个 \(DP\)。
设 \(dp_i\) 表示 \(\gcd = i\) 时变到 \(\gcd = 1\) 需要的期望步数。
显然：
行吧看来需要整的就是上边那一坨和式。
方便点设 \(f(i) = dp_i\)
这里停一下，有些长得帅的小伙伴不会推了（其实是我不会推了卡了我十几分钟qwq），我们发现从 \(j\) 开始的和式再化有些困难。
那我们这样：
首先不考虑 \(d | \frac{n}{k}\) ，显然原式（后面那一坨）为：
\[\sum_{d = 1}^{\left \lfloor \frac{m}{k} \right \rfloor}\left \lfloor \frac{m}{kd} \right \rfloor \mu(d) \]我们考虑把 \(d | \frac{n}{k}\) 限制条件加进去。
那我们发现一个显然的大小关系就是 \(\left \lfloor \frac{m}{k} \right \rfloor \ge \frac{n}{k}\)。
那这个 \(d\) 显然肯定都小于 \(\frac{n}{k}\)。
那我们只要被 \(\frac{n}{k}\) 整除的 \(d\) 就行了。
接着推：
\[\begin{aligned} &= \sum_{k | n}f(k)\sum_{d | \frac{n}{k}} \left \lfloor \frac{m}{kd} \right \rfloor \mu(d) \\ \end{aligned}\]然后小套路，设 \(x = kd\)
\[\begin{aligned} &= \sum_{k | n} f(k)\sum_{x | n} \left \lfloor \frac{m}{x} \right \rfloor \mu(\frac{x}{k}) \\ &= \sum_{x | n} \left \lfloor \frac{m}{x} \right \rfloor \sum_{k | x} f(k) \mu(\frac{x}{k}) \end{aligned}\]然后我们就发现后面这一坨是一个狄利克雷卷积。
设 \(g = f * \mu\)。
对于 \(1 \dots m\) 枚举每个数的约数是 \(n \ln n\) 的。
所以直接暴力统计即可。
\[\therefore f(i) = \frac{\sum\limits_{x | n} \left \lfloor \frac{m}{x} \right \rfloor g(x)}{m} + 1 \]他上面好像统计了 \(\left \lfloor \frac{m}{i} \right \rfloor f(i)\) 欸。不是这个我显然要把他放到左边去吧。我能计算出来的上面式子包含不出这个东西。
设 \(\sum\limits_{x | n} \left \lfloor \frac{m}{x} \right \rfloor g(x)(x \not= i) = ans\)
则：
\[f(i) - \frac{\left \lfloor \frac{m}{i} \right \rfloor}{m}f(i) = \frac{ans}{m} + 1 \]现在好像真做完了。
Code
#include <bits/stdc++.h>
typedef long long ll ;
using namespace std ;
const int N = 1e5 + 100 ;
const int mod = 1e9 + 7 ;
int prime[N] , tot , m ;
bool used[N] ;
ll f[N] , Mobius[N] , Convol[N] ;
ll nueyong[N << 1] ;
vector <int> factor[N] ;
void Linear_Mobius() {
Mobius[1] = 1 ; nueyong[1] = 1 ;
for (int i = 2 ; i < N ; ++ i) {
if (!used[i]) {
prime[++ tot] = i , Mobius[i] = -1 ;
}
for (int j = 1 ; j <= tot && prime[j] * i < N ; ++ j) {
used[i * prime[j]] = 1 ;
if (i % prime[j] == 0) {
Mobius[i * prime[j]] = 0 ;
break ;
}
Mobius[i * prime[j]] = - Mobius[i] ;
}
}
for (int i = 2 ; i < (N << 1) ; ++ i) {
nueyong[i] = 1ll * (mod / i) * (mod - nueyong[mod % i]) % mod ;
}
}
signed main() {
ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
cin >> m ; Linear_Mobius() ;
for (int i = 1 ; i <= m ; ++ i) {
for (int j = 1 ; i * j <= m ; ++ j) {
factor[i * j].push_back(i) ;
}
}
ll ans = 0 , Answer = 0 ;
for (int i = 2 ; i <= m ; ++ i) {
ans = 0 ;
for (auto j : factor[i]) (ans += (m / j) * Convol[j]) %= mod ;
f[i] = ((ans + m) * nueyong[m - (m / i)]) % mod ;
for (int k = i ; k <= m ; k += i) Convol[k] = (Convol[k] + Mobius[k / i] * f[i] + mod) % mod ;
(Answer += f[i]) %= mod ;
}
Answer = ((Answer * nueyong[m]) + 1) % mod ;
cout << Answer ;
}