牛客挑战赛47 F-简单题 莫比乌斯反演

传送门：https://ac.nowcoder.com/acm/contest/10743/F

题意

$$求解\sum_{i=1}^n\sum_{j=1}^mgcd(i,j)\mu(ij)\varphi (ij)$$

思路

根据积性函数和$\mu$的性质，只有i和j互质时才有贡献，不然$\mu(ij)=0$ i和j互质时，$\varphi (ij)=\varphi (i)\varphi (j)\;\;\mu(ij)=\mu(i)\mu(j)\;\;gcd(i,j)=1$

根据上述可得：

$$\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=1]\varphi (i)\mu(i)\varphi (j)\mu(j)$$ $设f(i)=\varphi (i)*\mu(i)，g(j)=\varphi (j)*\mu(j)，则$

$$\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)=1]f(i)g(j)$$

$$\sum_{i=1}^n\sum_{j=1}^mf(i)g(j)\sum_{di\;dj}\mu(d)$$

交换枚举顺序：

$$\sum_{d=1}^{min(n,m)}\mu(d)\sum_{i=1}^nf(i)[di]\sum_{j=1}^mg(j)[dj]$$

根据上式，可以预处理$\varphi,\mu,f,g$函数。然后暴力求解，即：

1
2
3
4
5
6
7
8
9
10
11
12
int n, m; cin >> n >> m;
for(int i = 1;i <= n; i++) f[i] = phi[i];
for(int j = 1;j <= m; j++) g[j] = phi[j];
ll ans = 0;

for(int d = 1;d <= min(n, m); d++) {
    if(!mu[d]) continue;
    ll sum1 = 0, sum2 = 0;
    for(int i = d;i <= n; i += d) sum1 += f[i];
    for(int j = d;j <= m; j += d) sum2 += g[j];
    ans = (ans + sum1 \* sum2 \* mu[d]) ;
}

但是这样会T掉，因为d=1时，n过大，那复杂度就是$O(n^2)$了。

需要 Dirichlet 前缀和优化即可。这是前缀和的几个版本：Dirichlet 前缀和

Dirichlet 前缀和优化之后的复杂度为$O(n\log \log n)$，完全可以接受。

Code(2512 MS)

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
##include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod = (1ll << 32);
const int N = 2e7 + 10;

int cnt;
int prime[N];
bool is_prime[N];
int mu[N];
int phi[N];

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

    for(int i = 1;i < N; i++) phi[i] *= mu[i];

}

int f[N], g[N];

void solve() {
    int _; cin >> _;
    init();
    while(_--) {
        int n, m; cin >> n >> m;
        for(int i = 1;i <= n; i++) f[i] = phi[i];
        for(int j = 1;j <= m; j++) g[j] = phi[j];

        ll ans = 0;

        for(int i = 1;i <= cnt; i++) {
            for(int j = n / prime[i];j >= 1; j--) f[j] += f[j * prime[i]];
            for(int j = m / prime[i];j >= 1; j--) g[j] += g[j * prime[i]];
        }

        for(int i = 1;i <= min(n, m); i++) {
            ans += 1ll * f[i] * g[i] * mu[i] % mod;
            ans %= mod;
        }
        cout << (ans + mod) % mod << endl;
    }
}

signed main() {
    solve();
    return 0;
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2021/01/12/nowcoder-challenge47-f/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！