题目描述

        Vivek initially has an empty array a and some integer constant m.
        He performs the following algorithm:
        Select a random integer x uniformly in range from 1 to m and append it to the end of a.
        Compute the greatest common divisor of integers in a.

  • In case it equals to 1, break
  • Otherwise, return to step 1.

        Find the expected length of a. It can be shown that it can be represented as $\frac {P}{Q}$ where $P$ and $Q$ are coprime integers and $Q≠0(mod {10^9+7})$. Print the value of $ P⋅Q^{-1}(mod 10^9+7)$.

输入输出格式

        The first and only line contains a single integer $m (1≤m≤100000)$.
        Print a single integer — the expected length of the array a written as $P⋅Q^{−1}(mod10^9+7)$.

输入输出样例

Sample input

4

Sample ouput

333333338

题解

        莫比乌斯和DP结合的好题。
        规定$dp[i]$为前面最大公因数为$i$，然后后来能够扩展的期望长度。显然$dp[1]=0$，然后有：

        这一步应该很好推。
        考虑到最大公因数也是自己的因数，那么就可以将上式化成这样：

        这里定义$f(x,d)$为$1$到$m$中有多少$i$使得$gcd(i,x)=d$，这里先不管这个$f(x,d)$，继续推下去。这里发现右式也含有$dp[x]$，这显然不利于递推，把它单独拿出来：

        然后：

        现在右侧的$DP$值都是小于$x$的了，于是可以递推出所有的$DP$值。
        下面考虑求$f(x,d)$，它即为：

        然后设出一个$g(x,d)$，表示：

        显然有：

        莫比乌斯反演一步：

        这里需要注意一点，当$p$不是$x$的因子时$g(x,p)$为0，否则就是$\lfloor\frac {m} {p}\rfloor$。
        于是加一些限制条件：

        这里的$p$就是$\frac {x} {d}$的所有因子，这样就可以在$O(logn)$复杂度下求出，再结合上面的$DP$递推式，本题就得以解决。答案就是：

        注：这里需要预处理因子，降分解质因子复杂度为$O(nlogn)$，总复杂度为$O(nlog^2n)$。

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 <bits/stdc++.h>

#define MOD 1000000007
#define N 100005
using namespace std;
int prim[N + 5], tot, mark[N + 5], mu[N + 5], dp[N + 5];
vector<int> vvp[N + 5];

inline void getMu() {
    mu[1] = 1;
    for (int i = 2; i <= N; i++) {
        if (!mark[i])prim[++tot] = i, mu[i] = -1;
        for (int j = 1; j <= tot; j++) {
            if (i * prim[j] > N)break;
            mark[i * prim[j]] = 1;
            if (i % prim[j] == 0)break;
            else mu[i * prim[j]] = -mu[i];
        }
    }
}

int getF(int a, int b, int d) {
    b /= d;
    int ans = 0;
    for (int i = 0; i < vvp[b].size(); i++)ans += mu[vvp[b][i]] * (a / vvp[b][i] / d);

    return ans + mu[b] * (a / b / d);
}

inline int qPow(int x, int y = MOD - 2) {
    int ans = 1, sta = x;
    while (y) {
        if (y & 1)ans = 1ll * ans * sta % MOD;
        sta = 1ll * sta * sta % MOD, y >>= 1;
    }
    return ans;
}

int main() {
    int m;
    cin >> m;
    getMu();
    for (int i = 1; i <= m; i++)for (int j = 2; i * j <= m; j++)vvp[i * j].push_back(i);//预处理因子
    for (int i = 2; i <= m; i++) {
        for (int s = 0; s < vvp[i].size(); s++)
            dp[i] = (1ll * dp[i] + 1ll * dp[vvp[i][s]] * getF(m, i, vvp[i][s]) % MOD) % MOD;
        dp[i] = (1ll * dp[i] + m) % MOD, dp[i] = 1ll * dp[i] * qPow(m - getF(m, i, i)) % MOD;
    }
    int ans = 0;

    for (int i = 1; i <= m; i++)ans = (1ll * ans + dp[i]) % MOD;
    cout << (1ll * ans * qPow(m) % MOD + 1 + MOD) % MOD;
    return 0;
}