我们可以现预处理出来所有的约数和,离线处理询问,按照 a 排序,当约数和小于当前寻问的 a 时,考虑它对答案的影响,若当前为 i,那么他会对 2i,3i...ki 位置的数造成影响,考虑用树状数组来维护 i∣d∑μ(⌊id⌋)g(i)每一次询问前更新树状数组,然后查询前缀和即可
代码
#include<iostream> #include<cstdio> #include<algorithm> #define lowbit(x) (-(x) & (x)) using namespace std; const int N = 1e5 + 5; typedef long long ll; const ll MOD = (ll)1 << 31;
bool st[N]; ll d[N], tr[N], ans[N]; int prime[N], mu[N], tot;
void add(int x, int k) { while (x < N) { tr[x] += k; x += lowbit(x); } }
ll query(int x) { ll res = 0; while (x) { res += tr[x]; x -= lowbit(x); } return res; }
void add2(int x) { for (int i = 1; i * x < N; i++) add(i * x, mu[i] * d[x]); }
struct que { int n, m, a, id; void init(int i) { scanf("%d%d%d", &n, &m, &a); id = i; } bool operator < (const que temp) const { return a < temp.a; } } Q[N], di[N];
void init() { mu[1] = 1; for (int i = 2; i < N; i++) { if (!st[i]) prime[++tot] = i, mu[i] = -1; for (int j = 1; i * prime[j] < N; j++) { st[i * prime[j]] = true; if (i % prime[j] == 0) break; mu[i * prime[j]] = -mu[i]; } } for (int i = 1; i < N; i++) for (int j = i; j < N; j += i) d[j] += i; for (int i = 1; i < N; i++) di[i].id = i, di[i].a = d[i]; sort(di + 1, di + N); }
int main() { init(); int q; scanf("%d", &q); for (int i = 1; i <= q; i++) Q[i].init(i); sort(Q + 1, Q + 1 + q); int t = 0; for (int i = 1; i <= q; i++) { while (di[t + 1].a <= Q[i].a && t + 1 < N) t++, add2(di[t].id); int n = Q[i].n, m = Q[i].m; int k = min(n, m); for (int l = 1, r; l <= k; l = r + 1) { r = min(k, min(n / (n / l), m / (m / l))); ans[Q[i].id] += (ll)(n / l) * (m / l) * (query(r) - query(l - 1)); } } for (int i = 1; i <= q; i++) printf("%lld\n", ans[i] % MOD); return 0; }