DDOSvoid's Blog

hdu 4947 GCD Array

发表于 分类于
本文字数： 2k 阅读时长 ≈ 2 分钟

题目描述

https://acm.hdu.edu.cn/showproblem.php?pid=4947

简要题意：给定 $n$ 和 $m$，有 $m$ 次操作，每次操作要么给出 $x,y,z$，对于所有 $(i,x)=y$ 的 $a_i$ 加上 $z$，要么给定 $x$，查询 $\sum_{i=1}^x a_i$

$n,m\le 5\times 10^4$

Solution

我们考虑对于位置 $k$​​，我们的加上 $z[(k,x)=y]$​，按照莫反的套路得到 $z\sum_{d|\frac{x}{y},dy|x}\mu(d)$​

我们考虑枚举 $\frac{x}{y}$ 的约数，然后对于所有 $dy$ 的倍数都加上 $z\mu(d)$，我们可以将倍数增加，改成单点加，这样我们在查询的时候需要查询约数和，这里的复杂度为 $O(\sqrt n\log n)$

那么前缀和的形式变成了 $\sum_{i=1}^x\lfloor\frac{x}{i}\rfloor a_i$，我们数论分块，复杂度仍然是 $O(\sqrt n\log n)$

总的时间复杂度 $O(n\sqrt n\log n)$，似乎有 $O(n\sqrt {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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#define maxn 50010
#define maxm 200010
#define ll long long
#define lowbit(i) ((i) & (-i))
using namespace std;

int pri[maxm], mu[maxm], cnt;
bool isp[maxm]; vector<int> d[maxm];
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];
        }
    }
    for (int i = 1; i <= n; ++i)
        for (int j = i; j <= n; j += i) d[j].push_back(i);
}

int n, m; 

ll Bit[maxn];
void add(int i, int v) { while (i <= n) Bit[i] += v, i += lowbit(i); }

ll get_sum(int i) {
    ll s = 0;
    while (i) s += Bit[i], i -= lowbit(i);
    return s; 
}

inline void solve_1() {
    int x, y, z; cin >> x >> y >> z;
    if (x % y) return ;
    for (auto t : d[x / y]) add(t * y, mu[t] * z); 
}

inline void solve_2() {
    int x; cin >> x; ll ans = 0; 
    for (int l = 1, r; l <= x; l = r + 1) {
        r = x / (x / l);
        ans += x / l * (get_sum(r) - get_sum(l - 1));
    } cout << ans << "\n";
}

int icase;
void work() { cout << "Case #" << ++icase << ":\n";
    for (int i = 1; i <= n; ++i) Bit[i] = 0; 
    for (int i = 1; i <= m; ++i) {
        int opt; cin >> opt;
        if (opt == 1) solve_1();
        else solve_2(); 
    }
}

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    init_isp(200000);
    while (cin >> n >> m && n + m) work(); 
    return 0;