$$\sum_{i=1}^{n}\sum_{j=1}^{m}\sigma_{1}(\gcd(i, j))[\sigma_1(\gcd(i,j))\leq a]$$
首先忽略 $\sigma_1(\gcd(i,j))\leq a$ 的限制
即求$$\sum_{i=1}^{n}\sum_{j=1}^{m}\sigma_{1}(\gcd(i, j))$$
$$=\sum_{d=1}^{\min\{n,m\}}\sigma_{1}(d)\sum_{i=1}^{n}\sum_{j=1}^{m}[(i,j)=d]$$
$$=\sum_{d=1}^{\min\{n,m\}}\sigma_{1}(d)\sum_{d'=1}^{\min\{\lfloor\frac{n}{d}\rfloor,\lfloor\frac{m}{d}\rfloor\}}\mu(d')\lfloor\frac{n}{dd'}\rfloor\lfloor\frac{m}{dd'}\rfloor$$
$$=\sum_{T}\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum_{d|T}\sigma_1(d)\mu(\frac{T}{d})$$
设 $f(n)=\sum_{d|n}\sigma_1(d)\mu(\frac{n}{d})$,要维护这个的前缀和,会受 $\sigma_1(\gcd(i,j))\leq a$ 的就只有这里的 $\sigma_1(d)$,离线一下询问,用树状数组维护这个前缀和,然后就像扫描线一样去修改这个前缀和,总共需要修改 $n\log n$ 次,所以复杂度为 $O(n\log ^2 n)$
#include <bits/stdc++.h> namespace IO { char buf[1 << 21], buf2[1 << 21], a[20], *p1 = buf, *p2 = buf, hh = '\n'; int p, p3 = -1; void read() {} void print() {} inline int getc() { return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++; } inline void flush() { fwrite(buf2, 1, p3 + 1, stdout), p3 = -1; } template <typename T, typename... T2> inline void read(T &x, T2 &... oth) { T f = 1; x = 0; char ch = getc(); while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getc(); } while (isdigit(ch)) { x = x * 10 + ch - 48; ch = getc(); } x *= f; read(oth...); } template <typename T, typename... T2> inline void print(T x, T2... oth) { if (p3 > 1 << 20) flush(); if (x < 0) buf2[++p3] = 45, x = -x; do { a[++p] = x % 10 + 48; } while (x /= 10); do { buf2[++p3] = a[p]; } while (--p); buf2[++p3] = hh; print(oth...); } } // using namespace IO const int N = 1e5; int prime[N + 7], prin, mu[N + 7], n, d[N + 7]; bool vis[N + 7]; std::pair<int, int> p[N + 7]; void init() { mu[1] = 1; for (int i = 2; i <= N; i++) { if (!vis[i]) { prime[++prin] = i; mu[i] = -1; } for (int j = 1; j <= prin && i * prime[j] <= N; j++) { vis[i * prime[j]] = 1; if (i % prime[j] == 0) break; mu[i * prime[j]] = -mu[i]; } } for (int i = 1; i <= N; i++) for (int j = 1; 1LL * i * j <= N; j++) d[i * j] += i; for (int i = 1; i <= N; i++) { p[i].first = d[i], p[i].second = i; } std::sort(p + 1, p + 1 + N); } struct Bit { unsigned tree[N]; int lowbit(int x) { return x & -x; } void add(int x, unsigned v) { for (int i = x; i <= N; i += lowbit(i)) tree[i] += v; } unsigned query(int x) { unsigned ans = 0; for (int i = x; i; i -= lowbit(i)) ans += tree[i]; return ans; } } bit; struct QUERY{ int n, m, a, id; bool operator < (const QUERY &p) const { return a < p.a; } } que[N]; unsigned ans[N]; unsigned solve(int n, int m) { unsigned ans = 0; for (int i = 1, j; i <= std::min(n, m); i = j + 1) { j = std::min(n / (n / i), m / (m / i)); ans += 1u * (n / i) * (m / i) * (bit.query(j) - bit.query(i - 1)); } return ans; } int main() { init(); int q; IO::read(q); for (int i = 1; i <= q; i++) { IO::read(que[i].n, que[i].m, que[i].a); que[i].id = i; } std::sort(que + 1, que + 1 + q); int cur = 1; for (int i = 1; i <= q; i++) { while (cur <= N && p[cur].first <= que[i].a) { for (int j = 1; j * p[cur].second <= N; j++) bit.add(j * p[cur].second, p[cur].first * mu[j]); cur++; } ans[que[i].id] = solve(que[i].n, que[i].m); } for (int i = 1; i <= q; i++) IO::print(ans[i] & ((1u << 31) - 1)); IO::flush(); return 0; }View Code