BZOJ 3529
题意：给定多组$n,m,a$，设$d_1(n)$为$n$约数和，求
$$
\sum_{i=1}^n \sum_{j=1}^m d_1(\gcd(i, j))
$$
并且满足$d_1(\gcd(i, j)) \leq a$
不考虑$a$的限制，枚举约数
$$
\sum_{d=1}^n \sum_{i=1}^n \sum_{j=1}^m d_1(d)[gcd(i,j)=d]
$$
发现$d_1(d)$与$i,j$无关，移到前面
$$
\sum_{d=1}^n d_1(d) \sum_{i=1}^n \sum_{j=1}^m [gcd(i,j)=d]
$$
将后面用反演套路化简，得
$$
\sum_{d=1}^n d_1(d) \sum_{k=1}^{\lfloor \frac nd \rfloor} \mu(k) \lfloor \frac n{kd} \rfloor \lfloor \frac m{kd} \rfloor
$$
设$T=kd$，则
$$
\sum_{T=1}^n \lfloor \frac nT \rfloor \lfloor \frac mT \rfloor \sum_{d|T}d_1(d) \mu(\frac Td)
$$
如果没有$a$的限制，则线性筛后面的函数即可。
考虑$a$的限制。
只有$d_1(x) \leq a$的才会有贡献。
所以将$d_1(x)$从小到大排序，将询问离线后按$a$从小到大排序
每次按照$a$的单增补齐到$a$，补齐即枚举$x$的倍数进行增加。
维护一个单调修改区间查值的数据结构，用树状数组维护之。
时间复杂度：$O(n\log ^2 n + q \sqrt n \log n)$
知识点：
1、枚举因数非常常用
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 100000 + 5;
struct data {
int n, m, a, id;
bool operator < (const data &rhs) const {return a < rhs.a;}
}qry[20000 + 5];
int mu[MAXN], pri[MAXN], vis[MAXN], tot;
int e[MAXN], ans[MAXN];
pair<int, int > d1[MAXN];
int Q;
int a[MAXN];
int min(int x, int y) {return x < y ? x : y;}
int lowbit(int x) {return x & (-x);}
int query(int x) {
int ret = 0;
for (int i = x; i; i -= lowbit(i)) ret += a[i];
return ret;
}
void add(int x, int v) {
for (int i = x; i <= 100000; i += lowbit(i)) a[i] += v;
}
int cal(int n, int m) {
int l = 1, ret = 0;
while (l <= n) {
int r = min(n / (n / l), m / (m / l));
ret = ret + (n / l) * (m / l) * (query(r) - query(l - 1));
l = r + 1;
}
/*for (LL d = 1; d <= n; ++d) {
ret = (ret + (n / d) * (m / d) % MO * (query(d) - query(d - 1) + MO) % MO) % MO;
}*/
return ret;
}
void init() {
ms(mu, 0), ms(pri, 0), ms(vis, 0), ms(e, 0), tot = 0;
mu[1] = 1, d1[1] = make_pair(1, 1), e[1] = 1;
for (int i = 2; i <= 100000; ++i) {
if (!vis[i]) pri[++tot] = i, d1[i] = make_pair(i + 1, i), e[i] = i + 1, mu[i] = -1;
for (int j = 1; j <= tot && (LL)i * pri[j] <= 100000ll; ++j) {
vis[i * pri[j]] = 1;
if (i % pri[j] == 0) {
mu[i * pri[j]] = 0;
d1[i * pri[j]] = make_pair(d1[i].first / e[i] * (e[i] * pri[j] + 1), i * pri[j]);
e[i * pri[j]] = e[i] * pri[j] + 1;
break ;
} else {
mu[i * pri[j]] = mu[i] * mu[pri[j]];
d1[i * pri[j]] = make_pair(d1[i].first * d1[pri[j]].first, i * pri[j]);
e[i * pri[j]] = pri[j] + 1;
}
}
}
}
void clean() {
ms(a, 0);
}
int solve() {
clean();
scanf("%d", &Q);
for (int i = 1; i <= Q; ++i) {
scanf("%d%d%d", &qry[i].n, &qry[i].m, &qry[i].a);
if (qry[i].n > qry[i].m) swap(qry[i].n, qry[i].m);
qry[i].id = i;
}
sort(qry + 1, qry + 1 + Q);
sort(d1 + 1, d1 + 1 + 100000);
int now = 1;
for (int i = 1; i <= Q; ++i) {
while (d1[now].first <= qry[i].a) {
for (int j = d1[now].second; j <= 100000; j += d1[now].second)
add(j, (d1[now].first * mu[j / d1[now].second]));
++now;
}
ans[qry[i].id] = cal(qry[i].n, qry[i].m);
}
for (int i = 1; i <= Q; ++i) printf("%d\n", ans[i] & (~(1 << 31)));
return 0;
}
}
int main() {
flyinthesky::init();
flyinthesky::solve();
return 0;
}
