Processing math: 100%


BZOJ3529 「SDOI2014」数表


Description

T 组询问,定义 F(n)=d|nd。每次给出 n,m,a

in,jmi=1,j=1,F(gcd(i,j))aF(gcd(i,j))

T20000;n,m,a105

Solution

首先 F 可以直接暴力地 O(nlogn) 筛出来。

考虑 a 的限制不是很好处理,假设没有这个 a 的限制,则所求为

ni=1mj=1F(gcd(i,j))

G(i)=nx=1my=1[gcd(x,y)=i]。这个东西是什么呢?在 这里 有它的推导过程。根据里面的过程,可以得到 G(i)=nid=1μ(d)nidmid(默认 nm
令下面的过程中t=id,则所求的是

ni=1F(i)G(i)=ni=1F(i)nid=1μ(d)nidmid=ni=1F(i)i|tμ(ti)ntmt=nt=1ntmti|tF(i)μ(ti)

观察后面的式子,正好是一个狄利克雷卷积的形式。这种样子的都可以类似于那种 O(nlogn) 地质数筛法在调和级数内求出来,再结合分块就可以做完这个没有 a 的题。

现在有了 a 的限制之后,离线。把询问按照 a 从小到大排序,然后按照 F(i) 从小到大加入。每当有一个新的 a ,就可以移动指针,将一些 F 用处理 i|tF(i)μ(ti) 的方式加入到这个里面。然后加入完之后用分块计算就行。

现在需要维护单点操作,查询前缀和,树状数组是不错的选择。

由于取模是 2321 ,可以直接 int 自然溢出最后和 2147483647 取一个 & 就行了。

时间复杂度:O(n+nlogn+nlog2(n)+Tlog(n)n)

Code

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
#include <bits/stdc++.h>
using namespace std;
const int N = 100000;
int T, cnt, flag[N + 5], p[N + 5], F[N + 5], mu[N + 5], ans[N + 5];
inline void prework() {
flag[1] = mu[1] = 1;
for(int i = 2; i <= N; i++) {
if(!flag[i]) { p[++cnt] = i, mu[i] = -1; }
for(int j = 1; j <= cnt && i * p[j] <= N; j++) {
flag[i * p[j]] = 1; if(i % p[j] == 0) {
mu[i * p[j]] = 0; break ;
} mu[i * p[j]] = mu[i] * -1;
}
}
for(int i = 1; i <= N; i++)
for(int j = i; j <= N; j += i) F[j] += i;
}
int c[N + 5];
inline int lb(int x) { return x & (-x); }
inline void add(int x, int d) {
for(int i = x; i <= N; i += lb(i)) c[i] += d;
}
inline int sum(int x) {
int ret = 0;
for(int i = x; i; i -= lb(i))
ret += c[i]; return ret;
}
inline int calc(int n, int m) {
int ret = 0;
for(int l = 1, r; l <= min(n, m); l = r + 1) {
r = min(n / (n / l), m / (m / l));
ret += (n / l) * (m / l) * (sum(r) - sum(l - 1));
} return ret;
}
struct Query {
int n, m, a, id;
inline bool operator < (const Query &x) const {
return a < x.a;
}
}Q[N + 5];
struct node {
int id, d;
inline bool operator < (const node &x) const {
return d < x.d;
}
}A[N + 5];
int main() {
prework(); scanf("%d", &T);
for(int i = 1; i <= T; i++) scanf("%d %d %d", &Q[i].n, &Q[i].m, &Q[i].a), Q[i].id = i;
for(int i = 1; i <= N; i++) A[i].d = F[i], A[i].id = i;
sort(Q + 1, Q + T + 1); sort(A + 1, A + N + 1); int pos = 0;
for(int i = 1; i <= T; i++) {
while(pos < N && A[pos + 1].d <= Q[i].a) {
++pos;
for(int j = 1; A[pos].id * j <= N; j++)
add(j * A[pos].id, A[pos].d * mu[j]);

} ans[Q[i].id] = calc(Q[i].n, Q[i].m);
}
for(int i = 1; i <= T; i++) printf("%d\n", ans[i] & 2147483647);
return 0;
}