CF1139D Steps to One

考虑枚举第一个数 $x$ ，分解质因数有 $p _ 1 ^ {c _ 1} \times p _ 2 ^ {c _ 2} \times \ldots \times p _ k ^ {c _ k}$ ，那么继续选择数的过程即为在每一个 $p$ 中选择一些指数删除。答案即为最后一个被删除的 $p$ 的删除次数，设为 $t _ i$ 。那么答案为 $f(S) = \max _ {i \in S} t _ i $ ，设 $g(S) = \min_ {i \in S} t _ i$。考虑 Min-Max 反演，那么有：

$$
f(S) = \max _ {i \in S} t _ i = \sum _ {T \in S} (-1) ^ {|T| + 1} g(T)
$$

考虑 $g(S)$ 的意义，对于任意一个选择的数如果是集合 $S$ 内所有数的倍数，那么答案加 $1$ ，否则一定和其中某一个数互质，则结束。设乘积 $y = \prod _ {i \in S} i$ ，那么有 $\lfloor \frac n y \rfloor$ 个数是 $y$ 的倍数，直到选择到了第一个非 $y$ 的倍数结束，概率为 $\frac {n - \lfloor \frac n y \rfloor} n$ ，则期望为 $\frac n {n - \lfloor \frac n y \rfloor}$ 。

那么有

$$
f(S) = \sum _ {T \in S} (-1) ^ {|T| + 1} \frac n {n - \lfloor \frac n {\prod _ {i \in S} i} \rfloor}
$$

考虑枚举每一个数，如果某一个质数的指数大于 $1$ ，则 $\mu = 0$ 。否则 $\mu$ 的定义和上式形式很相似，有：

$$
f(x) = - \sum _ {d | x} \mu(d) \frac n {n - \lfloor \frac n d \rfloor}
$$

那么答案为

$$
ANS = 1 + \frac {\sum _ {x = 1} ^ n } n = \frac {- \sum _ {x = 1} ^ n \sum _ {d | x} \mu(d) \frac n {n - \lfloor \frac n d \rfloor}} n
$$

考虑每一个 $d$ 的贡献，次数为 $\lfloor \frac n d \rfloor $ ，答案为

$$
ANS = 1 -\sum _ {d = 2} ^ n \mu(d) \frac {\lfloor \frac n d \rfloor} {n - \lfloor \frac n d \rfloor}
$$

对于 $d = 1$ 的情况，即对应上面 $|T| = 0$ 的情况，即选择的集合为空集，$x = 1$ ，直接结束没有贡献。

查看代码

#include <cstdio>
#include <vector>
#define eb emplace_back
using namespace std;
template <class Type>
void read (Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type, class ...rest>
void read (Type &x, rest &...y) { read(x), read(y...); }
template <class Type>
void write (Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar('0' + x % 10);
}
typedef long long L;
const int N = 1e5 + 10, mod = 1e9 + 7;
int n, mu[N], inv[N];
void init ()
{
    mu[1] = 1;
    for (int i = 1; i <= n; ++i)
        for (int j = i * 2; j <= n; j += i)
            mu[j] -= mu[i];
    for (int i = 2; i <= n; ++i) mu[i] += mu[i - 1];
    inv[1] = 1;
    for (int i = 2; i <= n; ++i)
        inv[i] = -(L)(mod / i) * inv[mod % i] % mod;
}
int main ()
{
    read(n);
    init();
    int res = 1;
    for (int l = 2, r; l <= n; l = r + 1)
    {
        int x = n / l;
        r = n / x;
        res = (res - (L)x * inv[n - x] % mod * (mu[r] - mu[l - 1])) % mod;
    }
    write((res + mod) % mod);
    return 0;
}