【题解】[bzoj3853] GCD Array

维护一个序列,支持以下操作:

1、给定 $n,d,v$ ,对每个 $(x,n)=d$ 的 $a_x\text{+=}v$ 。

2、询问 $\sum _{i=1}^k a_i$

$n\leq 10^5$

很有意思的题目,解法也很简洁。


妙妙题,建立一个辅助数组 $f$,让 $a_i=\sum _{d|i}f_d$ 。

考虑每次加的操作,对于每个 $i$ 实际上是加上这个东西:

考虑对 $f$ 反演:

那么可以看出,其实每次操作就是对所有的 $k | \frac{n}{d}$ 的 $f_{kd}$ 加上了 $\mu(k)\cdot v$ .

考虑询问操作就是在询问

这个可以 $\sqrt n$ 分块来做。于是最后修改复杂度 $\sqrt[3] n\log n$,询问复杂度 $\sqrt n\log n$ 。 注意到可以调整块的大小,对于所有 $<\sqrt {x\log x}$ 的位置暴力加,对于所有 $>\sqrt {x\log x}$ 的位置,至多有 $\sqrt \frac{x}{\log x}$ 个。所以可以把 $\log $ 放到里面去。

当然我肯定是写 $\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
69
70
71
72
73
74
75
76
77
78
79
80
#include <bits/stdc++.h>

using namespace std ;

typedef long long ll ;

void debug(long long *tp, int minn, int maxn, char c){
for (int i = minn ; i <= maxn ; ++ i)
cout << tp[i] << " " ; cout << c ;
}

const int N = 200110 ;

namespace L_s{
int cnt ;
int pr[N] ;
int mu[N] ;
int smu[N] ;
int vis[N] ;
vector <int> fc[N] ;
void sieve(int U){
mu[1] = 1 ;
for (int i = 2 ; i <= U ; ++ i){
if (!vis[i]) mu[i] = -1, pr[++ cnt] = i ;
for (int j = 1 ; j <= cnt ; ++ j){
if (i * pr[j] > U) break ;
vis[i * pr[j]] = 1 ;
if (i % pr[j] == 0) break ;
mu[i * pr[j]] = -mu[i] ;
}
}
for (int i = 1 ; i <= U ; ++ i)
smu[i] = smu[i - 1] + mu[i] ;
for (int i = 1 ; i <= U ; ++ i)
for (int j = 1 ; i * j <= U ; ++ j)
fc[i * j].push_back(i) ;
}
}

int T ;
ll _bit[N] ;
int base[N] ;
int n, m, p ;

int low(int x){
return (x & (-x)) ;
}
void add(int x, int v){
for ( ; x <= n ; x += low(x)) _bit[x] += v ;
}
ll ask(int x){
ll ret = 0 ;
for ( ; x ; x -= low(x)) ret += (ll)_bit[x] ;
return ret ;
}
int main(){
int opt, x, d, v ;
L_s :: sieve(N - 10) ;
while (1){
cin >> n >> m ; ++ T ;
if (!(m + n)) return 0 ;
cout << "Case #" << T << ": " << '\n' ;
fill(_bit + 1, _bit + n + 1, 0) ;
while (m --){
scanf("%d%d", &opt, &x) ;
if (opt == 1){
scanf("%d%d", &d, &v) ; if (x % d != 0) continue ;
for (int i = 0 ; i < L_s :: fc[x / d].size() ; ++ i)
add(L_s :: fc[x / d][i] * d, L_s :: mu[L_s :: fc[x / d][i]] * v) ;
}
else {
ll ans = 0 ;
for (int l = 1, r ; l <= x ; l = r + 1)
r = x / (x / l), ans += (ask(r) - ask(l - 1)) * (ll)(x / l) ;
cout << ans << '\n' ;
}
}
}
return 0 ;
}