Description
T 组询问,定义 F(n)=∑d|nd。每次给出 n,m,a 求
i≤n,j≤m∑i=1,j=1,F(gcd(i,j))≤aF(gcd(i,j))T≤20000;n,m,a≤105
Solution
首先 F 可以直接暴力地 O(nlogn) 筛出来。
考虑 a 的限制不是很好处理,假设没有这个 a 的限制,则所求为
n∑i=1m∑j=1F(gcd(i,j))令 G(i)=n∑x=1m∑y=1[gcd(x,y)=i]。这个东西是什么呢?在 这里 有它的推导过程。根据里面的过程,可以得到 G(i)=⌊ni⌋∑d=1μ(d)⌊nid⌋⌊mid⌋(默认 n≤m)
令下面的过程中t=id,则所求的是
n∑i=1F(i)G(i)=n∑i=1F(i)⌊ni⌋∑d=1μ(d)⌊nid⌋⌊mid⌋=n∑i=1F(i)∑i|tμ(ti)⌊nt⌋⌊mt⌋=n∑t=1⌊nt⌋⌊mt⌋∑i|tF(i)μ(ti)观察后面的式子,正好是一个狄利克雷卷积的形式。这种样子的都可以类似于那种 O(nlogn) 地质数筛法在调和级数内求出来,再结合分块就可以做完这个没有 a 的题。
现在有了 a 的限制之后,离线。把询问按照 a 从小到大排序,然后按照 F(i) 从小到大加入。每当有一个新的 a ,就可以移动指针,将一些 F 用处理 ∑i|tF(i)μ(ti) 的方式加入到这个里面。然后加入完之后用分块计算就行。
现在需要维护单点操作,查询前缀和,树状数组是不错的选择。
由于取模是 232−1 ,可以直接 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; }
|