CF1139D Steps to One

$$ E\left( X \right) ,X\text{长度} \\ E\left( X \right) =\sum_{i\ge 1}{P\left( X\ge i \right)},i\text{是长度} \\ =1+\sum_{i\ge 2}{\frac{m^{i-1}-\sum_{1\le j\le m}{\mu \left( j \right) \lfloor \frac{m}{j} \rfloor ^{i-1}}}{m^{i-1}}}\left( \text{枚举长度}i\text{，钦定长度小于}i\text{的全都不互质} \right) \\ 1+\sum_{i\ge 1}{\frac{m^i-\sum_{1\le j\le m}{\mu \left( j \right) \lfloor \frac{m}{j} \rfloor ^i}}{m^i}} \\ 1+\sum_{i\ge 1}{\frac{m^i-m^i-\sum_{2\le j\le m}{\mu \left( j \right) \lfloor \frac{m}{j} \rfloor ^i}}{m^i}} \\ =1-\sum_{1\ge 1}{\frac{\sum_{2\le j\le m}{\mu \left( j \right) \lfloor \frac{m}{j} \rfloor ^i}}{m^i}} \\ 1-\sum_{2\le j\le m}{\mu \left( j \right) \sum_{1\ge 1}{\left( \frac{\lfloor \frac{m}{j} \rfloor}{m} \right) ^i}} \\ =1-\sum_{2\le j\le m}{\mu \left( j \right)}\frac{\lfloor \frac{m}{j} \rfloor}{m}\underset{n\rightarrow \infty}{\lim}\frac{1-\left( \frac{\lfloor \frac{m}{j} \rfloor}{m} \right) ^n}{1-\frac{\lfloor \frac{m}{j} \rfloor}{m}} \\ =1-\sum_{2\le j\le m}{\mu \left( j \right)}\frac{\lfloor \frac{m}{j} \rfloor}{m}\frac{1}{1-\frac{\lfloor \frac{m}{j} \rfloor}{m}} \\ =1-\sum_{2\le j\le m}{\mu \left( j \right)}\frac{\lfloor \frac{m}{j} \rfloor}{m-\lfloor \frac{m}{j} \rfloor} \\ $$

#include <cstring>
#include <iostream>
using int_t = long long int;
using std::cin;
using std::cout;
using std::endl;

const int_t mod = 1e9 + 7;
const int_t LARGE = 1e5;
int_t inv[LARGE + 1];
int_t m;
int_t mu[LARGE + 1];
int_t factor[LARGE + 1];
bool isPrime[LARGE + 1];

int main() {
    memset(isPrime, 1, sizeof(isPrime));
    cin >> m;
    inv[1] = 1;
    for (int_t i = 2; i <= m; i++)
        inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    for (int_t i = 2; i <= m; i++)
        if (isPrime[i]) {
            for (int_t j = i * i; j <= m; j += i) {
                factor[j] = i;
                isPrime[j] = false;
            }
            factor[i] = i;
        }
    mu[1] = 1;
    for (int_t i = 2; i <= m; i++) {
        int_t p = factor[i];
        if (i / p % p == 0)
            mu[i] = 0;
        else
            mu[i] = mu[i / p] * -1;
    }
    int_t result = 1;
    for (int_t i = 2; i <= m; i++) {
        int_t x = m / i;
        result = (result - mu[i] * x % mod * inv[m - x] % mod + mod) % mod;
    }
    cout << result << endl;
    return 0;
}