QwQ

### 题解

$$dp_x=1+\sum_{y=1}^m \frac {dp_{gcd(x,y)}}{n}$$

$$dp_x=1+\sum_{d|x} \frac{f_{x,d}dp_d}{n}$$

$d_1+…+d_n=nlogn$

#include<bits/stdc++.h>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define edge(i, u) for (int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define ls (u << 1)
#define rs (u << 1 | 1)
#define mod 1000000007
#define eps 1e-4
#define N 100005
using std::vector;
int n;
ll dp[N], ans, invn;
vector<int> d[N], f[N];
inline void sieve ()
{
fo (i, 1, n)
{
for (int j = i; j <= n; j += i)
d[j].pb(i);
std::reverse(d[i].begin(), d[i].end());
}
fo (i, 1, n)
{
int sz = d[i].size() - 1;
fo (j, 0, sz)
{
int now = n / d[i][j];
fo (k, 0, j - 1)
{
if (!(d[i][k] % d[i][j]))
now -= f[i][k];
}
f[i].pb(now);
}
}
}
inline ll pow (ll x, int y)
{
ll ret = 1;
while (y)
{
if (y & 1) ret = ret * x % mod;
x = x * x % mod;
y >>= 1;
}
return ret;
}
int main ()
{
scanf("%d", &n);
sieve();
invn = pow(n, mod - 2);
fo (i, 2, n)
{
int sz = d[i].size() - 1;
dp[i] = 1;
fo (j, 1, sz)
(dp[i] += dp[d[i][j]] * f[i][j] % mod * invn) %= mod;
dp[i] = dp[i] * pow((1 - f[i][0] * invn % mod + mod) % mod, mod - 2) % mod;
}
ans = 1;
fo (i, 1, n) (ans += dp[i] * invn) %= mod;
printf("%lld", ans);
return 0;
}