D. Steps to One
设 \(E(x)\) 为 \(x\) 的期望值,\(P(x)\) 为事件 \(x\) 发生的概率。
则
\[\begin{aligned} E(len) & = \sum_{i \ge 1} P(len = i) \cdot i \\ & = \sum_{i \ge 1} P(len = i) \sum_{j = 1}^i 1 \\ & = \sum_{j \ge 1} \sum_{i\ge j} P(len = i) \\ & = \sum_{i \ge 1} P(len \ge i) \end{aligned} \]发现
\[\sum_{i\ge 1} P(len = i) \]恰好就是整体情况,为 \(1\)。
所以
\[\begin{aligned} E(len) & = \sum_{i \ge 1} P(len \ge i) \\ & = 1 + \sum_{i \ge 1} P(len > i) \end{aligned} \]要使得 \(len > i\),则必须满足前 \(i\) 个数的 \(\gcd > 1\)。
于是
\[P(len > i) = P\left(\gcd_{j = 1}^i\{a_j\} > 1 \right) \]进行一个反面考虑
\[P\left(\gcd_{j = 1}^i \{a_j\} > 1 \right) = 1 - P\left(\gcd_{j = 1}^i \{a_j\} = 1 \right) \]那么
\[\begin{aligned} P(len > i) & = 1 - P\left(\gcd_{j = 1}^i \{a_j\} = 1 \right) \\ & = 1 - \dfrac{\sum_{a_1 = 1}^m \sum_{a_2 = 1}^m \cdots \sum_{a_i = 1}^m [\gcd_{j = 1}^i \{ a_j\} = 1]}{m^i} \\ & = 1 - \dfrac{\sum_{d = 1}^m \mu(d) \left\lfloor\dfrac{m}{d}\right\rfloor^i}{m^i} \end{aligned} \]单独将 \(d = 1\) 的情况拎出来,其值为 \(1\)。
\[P(len > i) = - \dfrac{\sum_{d = 2}^m \mu(d) \left\lfloor\dfrac{m}{d}\right\rfloor^i}{m^i} \]代回原式
\[\begin{aligned} E(len) & = 1 + \sum_{i \ge 1} P(i > len) \\ & = 1 + \sum_{i \ge 1} - \dfrac{\sum_{d = 2}^m \mu(d) \left\lfloor\dfrac{m}{d}\right\rfloor^i}{m^i} \\ & = 1 - \sum_{i \ge 1} \dfrac{1}{m^i} \sum_{d = 2}^m \mu(d) \left\lfloor\dfrac{m}{d}\right\rfloor^i \\ & = 1 - \sum_{d = 2}^m \mu(d) \sum_{i \ge 1} \left(\dfrac{\left\lfloor\frac{m}{d}\right\rfloor}{m} \right)^i \end{aligned} \]后面有一个无穷项等比数列求和
\[S = x + x^2 + x^3 + \cdots \\ xS = x^2 + x^3 + x^4 + \cdots \\ S - xS = x \\ S = \dfrac{x}{1 - x} \]所以
\[\begin{aligned} E(len) & = 1 - \sum_{d = 2}^m \mu(d) \dfrac{\frac{\left\lfloor\frac{m}{d}\right\rfloor}{m}}{1 - \frac{\left\lfloor\frac{m}{d}\right\rfloor}{m}} \\ & = 1 - \sum_{d = 2}^m \mu(d) \dfrac{\left\lfloor\frac{m}{d}\right\rfloor}{m - \left\lfloor\frac{m}{d}\right\rfloor} \end{aligned} \]\(\Theta(m)\) 计算即可,注意 \(m\) 比较小所以不需要整除分块。
// 18 = 9 + 9 = 18. #include <iostream> #include <cstdio> #include <cstring> #define Debug(x) cout << #x << "=" << x << endl typedef long long ll; using namespace std; namespace IO { int len = 0; char buf[(1 << 20) + 1], *S, *T; #if ONLINE_JUDGE #define Getchar() (S == T ? T = (S = buf) + fread(buf, 1, (1 << 20) + 1, stdin), (S == T ? EOF : *S++) : *S++) #else #define Getchar() getchar() #endif #define re register inline int read() { re char c = Getchar(); re int x = 0; while (c < '0' || c > '9') c = Getchar(); while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = Getchar(); return x; } } using IO::read; const int MAXN = 1e5 + 5; const int MOD = 1e9 + 7; int add(int a, int b) {return (a + b) % MOD;} int sub(int a, int b) {return (a - b + MOD) % MOD;} int mul(int a, int b) {return (ll)a * b % MOD;} int p[MAXN], mu[MAXN], inv[MAXN]; bool vis[MAXN]; void pre(int n) { mu[1] = 1; for (int i = 2; i <= n; i++) { if (!vis[i]) { p[++p[0]] = i; mu[i] = -1; } for (int j = 1; j <= p[0] && i * p[j] <= n; j++) { vis[i * p[j]] = true; if (i % p[j] == 0) { mu[i * p[j]] = 0; break; } mu[i * p[j]] = mu[i] * mu[p[j]]; } } inv[1] = 1; for (int i = 2; i <= n; i++) { inv[i] = mul(MOD - MOD / i, inv[MOD % i]); } } int main() { int m = read(); pre(m); int res = 0; for (int d = 2; d <= m; d++) { res = add(res, mu[d] * mul(m / d, inv[m - m / d])); } printf("%d\n", sub(1, res)); return 0; }