这里介绍期望dp + 莫比乌斯反演的做法

首先是期望dp，设 $f_{i}$ 为令 $gcd = i$ 的序列变成 $gcd=1$ 的序列的期望步数，$f_{1}=0$。

考虑反向转移

$$f_{i} =1 + \frac{\sum_{j=1}^{n} f_{gcd(i,j)} }{n}$$

令 $d = gcd(i,j)$，遍历 $d$

$$f_{i} =1 + \frac{\sum_{d|i} f_{d} \sum_{j=1}^{n} \left[gcd(i,j)==d \right] }{n}=1 + \frac{\sum_{d|i} f_{d} \sum_{j=1}^{\frac{n}{d}} \left[gcd(\frac{i}{d},j)==1\right] }{n} $$

因为 $\left[gcd(\frac{i}{d},j)==1\right]=\sum_{e|gcd(\frac{i}{d},j)}$，$e|gcd(\frac{i}{d},j)$ 等价于 $e|j \And e|\frac{i}{d}$

$$f_{i} =1 + \frac{\sum_{d|i} f_{d} \sum_{j=1}^{\frac{n}{d}} \sum_{e=1}^{n} \mu(e)\left[e|j \And e|\frac{i}{d} \right] }{n} $$

交换求和顺序

$$f_{i} = 1 + \frac{\sum_{d|i} f_{d} \sum_{e=1}^{n} \left[e|\frac{i}{d} \right]\mu(e)\sum_{j=1}^{\frac{n}{d}}\left[e|j \right] }{n}=1 + \frac{\sum_{d|i} f_{d} \sum_{e|\frac{i}{d}} \mu(e) \left \lfloor \frac{n}{ed} \right \rfloor}{n} $$

在向后转移，当 $i|j$ 时 会出现 $f_{i}$ 转移到 $f_{i}$ 的情况，我们需将其分离出来。易知每次都有 $\frac{\left\lfloor\frac{n}{i}\right\rfloor}{n}$ 的概率让 $gcd(i,j) = i$，即 i 保持不变，可以得到使 $gcd(i,j) \ne i$ 的期望步数为 $\frac{n}{n-\left\lfloor \frac{n}{i}\right\rfloor}$

$$f_{i} =\frac{n}{n-\left\lfloor \frac{n}{i}\right\rfloor} + \frac{\sum_{d|i,d<i} f_{d} \sum_{e|\frac{i}{d}} \mu(e) \left \lfloor \frac{n}{ed} \right \rfloor}{n-\left\lfloor \frac{n}{i}\right\rfloor} = \frac{n + \sum_{d|i,d<i} f_{d} \sum_{e|\frac{i}{d}} \mu(e) \left \lfloor \frac{n}{ed} \right \rfloor}{n-\left\lfloor \frac{n}{i}\right\rfloor} $$

这里可以预处理出 $1$ 到 $n$ 的所有数的全部约数，之后每次转移所需的时间为 O(lognlogn)，整体复杂度O(nlognlogn)

由于开始是没有数字被记录的，所以的最后期望为

$$ans = \frac{\sum_{i=1}^{n}f_{i}}{n}$$

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 10;
const int mod = 1e9 + 7;
int prime[N], isprime[N], cnt;
int mu[N];
ll dp[N];
int e[N*12], ne[N*12], h[N], idx;  //用邻接表来储存所有数的约数

void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

void init() {  
	for (int i = 1;i < N;i++) {
		for (int j = i;j < N;j += i) {
			add(j, i);
		}
	}
}

void getmu() {
	mu[1] = 1;
	for (int i = 2;i < N;i++) {
		if (!isprime[i]) {
			prime[cnt++] = i;
			mu[i] = -1;
		}
		for (int j = 0;j < cnt && i * prime[j] < N;j++) {
			isprime[i * prime[j]] = 1;
			if (i % prime[j] == 0) {
				mu[i * prime[j]] = 0;
				break;
			}
			mu[i * prime[j]] = -mu[i];
		}
	}
}

ll qmi(ll a, ll b) {
	ll ans = 1;
	while (b) {
		if (b & 1)ans = ans * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return ans;
}

int main() {
	init();  //得到所有数的约数
	getmu(); //线性筛出莫比乌斯函数
	int n;
	cin >> n;
	dp[1] = 0;
	for (int i = 2;i <= n;i++) {
		ll fz = n;
		for (int j = h[i];j != 0;j = ne[j]) { //遍历所有i的约数
			int d = e[j];
			if (d == i)continue;
			ll res = 0;
			for (int k = h[i / d];k != 0;k = ne[k]) { //遍历所有i/d的约数
				int g = e[k];
				res = (res + mu[g] * (n / g / d) + mod) % mod;
			}
			fz = (fz + res * dp[d]) % mod;
		}
		dp[i] = (fz * qmi(n - (n / i), mod - 2)) % mod;
	}

	ll ans = 1;
	ll inv = qmi(n, mod - 2);
	for (int i = 1;i <= n;i++) {
		ans = (ans + dp[i] * inv) % mod;
	}
	cout << ans << endl;
	return 0;
}