Description
\(T\) 组询问，定义 \(F(n)=\sum\limits_{d|n}d\)。每次给出 \(n,m,a\) 求
\[\sum\limits_{i=1,j=1,F(\gcd(i,j)) \leq a}^{i\leq n, j \leq m} F (\gcd(i,j))\]
\(T \leq 20000;n,m,a\leq 10^5\)
Solution
首先 \(F\) 可以直接暴力地 \(O(n \log n)\) 筛出来。
考虑 \(a\) 的限制不是很好处理，假设没有这个 \(a\) 的限制，则所求为
\[\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m} F (\gcd(i,j))\]
令 \(G(i)=\sum\limits_{x=1}^{n}\sum\limits_{y=1}^{m}[\gcd(x,y)=i]\)。这个东西是什么呢？在 有它的推导过程。根据里面的过程，可以得到 \(G(i) = \sum\limits_{d=1}^{\lfloor\frac{n}{i}\rfloor}\mu(d)\lfloor\frac{n}{id}\rfloor\lfloor\frac{m}{id}\rfloor\)（默认 \(n \leq m\)）
令下面的过程中\(t = id\)，则所求的是\[\begin{aligned}&\sum\limits_{i=1}^{n}F(i)G(i) \\ &= \sum\limits_{i=1}^{n}F(i)\sum\limits_{d=1}^{\lfloor\frac{n}{i}\rfloor}\mu(d)\lfloor\frac{n}{id}\rfloor\lfloor\frac{m}{id}\rfloor \\ &=\sum\limits_{i=1}^{n}F(i)\sum\limits_{i | t}\mu(\frac{t}{i})\lfloor\frac{n}{t}\rfloor\lfloor\frac{m}{t}\rfloor \\ &= \sum\limits_{t=1}^{n}\lfloor\frac{n}{t}\rfloor\lfloor\frac{m}{t}\rfloor\sum\limits_{i | t}F(i)\mu(\frac{t}{i})\end{aligned}\]
观察后面的式子，正好是一个狄利克雷卷积的形式。这种样子的都可以类似于那种 \(O(n \log n)\) 地质数筛法在调和级数内求出来，再结合分块就可以做完这个没有 \(a\) 的题。
现在有了 \(a\) 的限制之后，离线。把询问按照 \(a\) 从小到大排序，然后按照 \(F(i)\) 从小到大加入。每当有一个新的 \(a\) ，就可以移动指针，将一些 \(F\) 用处理 \(\sum\limits_{i | t}F(i)\mu(\frac{t}{i})\) 的方式加入到这个里面。然后加入完之后用分块计算就行。
现在需要维护单点操作，查询前缀和，树状数组是不错的选择。
由于取模是 \(2^{32} - 1\) ，可以直接 int 自然溢出最后和 \(2147483647\) 取一个 & 就行了。
时间复杂度：\(O(n + n \log n + n \log ^ 2 (n) + T \log (n)\sqrt n)\)
Code
#includeusing 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; }