题目描述
http://codeforces.com/problemset/problem/1139/D
简要题意：给定 $m$，每次随机选择一个 $1$ 到 $m$ 的整数，与手上的数取 $gcd$，求期望多少次手上的数变成 $1$
$m\le 10^5$
Solution
令 $f_n$ 表示 $n$ 变成 $1$ 的期望次数，容易得到 $f_n=1+\frac{1}{m}\sum_{d|n}f(d)\sum_{i=1}^m[(i,n)=d]$
这个式子拿莫反变一下能够得到 $f_n=1+\frac{1}{m}\sum_{T|n}\lfloor\frac{m}{T}\rfloor\sum_{t|T}f_t\mu(\frac{T}{t})$，后面的那个东西我们令其为 $g_n$
然后我们在求 $f_n$ 的时候只需要枚举约数即可，需要注意要把 $f_n$ 提出来，算完 $f_n$ 再更新 $g_n$ 即可
时间复杂度 $O(n\log n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| #include <iostream>
#include <vector>
#define maxn 100010
#define ll long long
using namespace std;
const int p = 1000000007;
ll pow_mod(ll x, ll n) {
ll s = 1;
for (; n; n >>= 1, x = x * x % p)
if (n & 1) s = s * x % p;
return s;
}
int pri[maxn], cnt, mu[maxn]; bool isp[maxn];
void init_isp(int n) {
mu[1] = 1;
for (int i = 2; i <= n; ++i) {
if (!isp[i]) pri[++cnt] = i, mu[i] = -1;
for (int j = 1; j <= cnt && i * pri[j] <= n; ++j) {
isp[i * pri[j]] = 1;
if (i % pri[j] == 0) break;
mu[i * pri[j]] = -mu[i];
}
}
}
int n;
ll f[maxn], g[maxn];
vector<int> d[maxn];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n; init_isp(n);
f[1] = g[1] = 0; ll inv = pow_mod(n, p - 2), ans = n;
if (n == 1) return cout << 1 << "\n", 0;
for (int i = 1; i <= n; ++i)
for (int j = i; j <= n; j += i) d[j].push_back(i);
for (int u = 2; u <= n; ++u) {
for (auto v : d[u])
if (u != v) f[u] = (f[u] + n / v * g[v]) % p;
for (auto v : d[u])
if (u != v) f[u] = (f[u] + n / u * f[v] * mu[u / v]) % p;
f[u] = (f[u] * inv + 1) % p * pow_mod(1 - n / u * inv % p, p - 2) % p;
for (auto v : d[u]) g[u] = (g[u] + f[v] * mu[u / v]) % p;
ans = (ans + f[u]) % p;
} cout << (ans * inv % p + p) % p << "\n";
return 0;
}
|