题目大意
计算
$$ \sum_{i=1}^n \sum_{j=1}^m \sigma_1(\gcd(i, j)) [\sigma_1(\gcd(i, j)) \leqslant a] $$
分析
若不考虑 $a$ 的限制，就是非常套路的 Mobius 反演
$$ ans = \sum_{d=1} \sigma_1(d) [d \leqslant a] \sum_{x=1} \mu(x) \left\lfloor \frac{n}{dx} \right\rfloor \left\lfloor \frac{m}{dx} \right\rfloor $$
但是这个 $a$ 的限制比较头疼。考虑 $y=dx$ 代换，有
$$ ans = \sum_{y=1} \left\lfloor \frac{n}{y} \right\rfloor \left\lfloor \frac{m}{y} \right\rfloor \sum_{d \mid y} \sigma_1(d) \mu\left(\frac{y}{d}\right) [d \leqslant a] $$
因此我们可以将询问対 $a$ 排序，后者使用树状数组维护。
int main() {
Euler(N);
int T;
cin >> T;
vector<i4> v(T);
for (int i = 0; i < T; i++) {
int n, m, a;
cin >> n >> m >> a;
v[i] = {n, m, a, i};
}
sort(v.begin(), v.end(), [](const i4 &l, const i4 &r) {
return std::get<2>(l) < std::get<2>(r);
});
fwtree<ll> tr(N);
auto add = [&](int x) {
auto [sgm, q] = sigma[x];
for (int i = 1; i * q < N; i++) {
tr.add(i * q, sgm * mu[i]);
}
};
int pos = 1;
vector<ll> ret(T);
for (auto [n, m, a, i] : v) {
while (sigma[pos].first <= a) {
add(pos++);
}
for (int l = 1, r; l <= min(n, m); l = r + 1) {
r = min(n / (n / l), m / (m / l));
ret[i] += tr.sum(l, r) * ll(n / l) * ll(m / l) % P;
}
}
for (auto ai : ret) {
cout << ai % P << '\n';
}
return 0;
}
全部代码请看：Luogu/3x/P3312.cpp。