显然题目所求为 \(\sum\limits_{i = 1}^n \sum\limits_{j = 1}^m [\sigma(\gcd(i,j)) \le a]\sigma(\gcd(i,j))\)。
先不考虑 \(a\) 的限制，推一推式子。
\[\begin{align*} & \sum\limits_{i = 1}^n \sum\limits_{j = 1}^m \sigma(\gcd(i,j)) \\ = & \sum\limits_{i = 1}^{\min(n,m)} \sigma(i) \sum\limits_{x = 1}^n \sum\limits_{y = 1}^m [\gcd(x,y) = i] \\ = & \sum\limits_{i = 1}^{\min(n,m)} \sigma(i) \sum\limits_{d | i} \mu(\dfrac i d) \lfloor \dfrac n d \rfloor \lfloor \dfrac m d \rfloor \\ = & \sum\limits_{i = 1}^{\min(n,m)} \lfloor \dfrac n i \rfloor \lfloor \dfrac m i \rfloor \sum\limits_{d | i} \sigma(d) \mu(\dfrac i d) \end{align*}\]
现在我们来考虑 \(a\) 的限制。
设 \(\text{sum}(i) = \sum\limits_{d | i} \sigma(d) \mu(\dfrac i d)\)，那么显然对于任意的 \(\sigma(i) \le a\)，它只会对满足 \(i | d\) 的 \(\text{sum}(d)\) 有贡献。
于是可以把 \(\sigma(i)\) 排序，并把询问离线按 \(a\) 排序，然后随着 \(a\) 的增大，不可能会有 \(\sigma(i)\) 的贡献消失，只可能会增加，所以枚举倍数并更新贡献即可。
这样的话，增加贡献的次数是 \(O(\sum\limits_{i = 1}^n\dfrac n i) \approx O(n \log n)\)。
接着考虑如何维护贡献。
由于要单点修改并且区间查询，必须在线，常数要求较高，当然首选 BIT。
此外，因为模数很特殊，所以自然溢出并在最后按位与 \(2^{31} - 1\) 即可。
好奇为什么约数和这种东西都要线性筛（
反正 \(O(n \log n)\) 随便跑，懒得推了。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
using namespace std;
const int N = 1e5;
const int Q = 2e4;
int q;
struct note
{
int n,m,a,id;
inline bool operator<(const note &o) const
{
return a < o.a || (a == o.a && id < o.id);
}
} a[N + Q + 5];
int cnt,prime[N + 5],vis[N + 5],mu[N + 5];
long long c[N + 5],ans[Q + 5];
inline void update(int x,long long k)
{
for(;x <= N;x += lowbit(x))
c[x] += k;
}
inline long long query(int x)
{
long long ret = 0;
for(;x;x -= lowbit(x))
ret += c[x];
return ret;
}
int main()
{
mu[1] = 1,a[1].id = -1;
for(register int i = 1;i <= N;++i)
{
a[i].id = -i;
for(register int j = 1;i * j <= N;++j)
a[i * j].a += i;
}
for(register int i = 2;i <= N;++i)
{
if(!vis[i])
prime[++cnt] = i,mu[i] = -1;
for(register int j = 1;j <= cnt && i * prime[j] <= N;++j)
{
vis[i * prime[j]] = 1;
if(!(i % prime[j]))
break;
mu[i * prime[j]] = -mu[i];
}
}
scanf("%d",&q);
for(register int i = 1;i <= q;++i)
scanf("%d%d%d",&a[N + i].n,&a[N + i].m,&a[N + i].a),a[N + i].id = i;
sort(a + 1,a + N + q + 1);
for(register int i = 1,tot = 0;i <= N + q;++i)
if(a[i].id < 0)
{
a[i].id = -a[i].id;
for(register int j = 1;a[i].id * j <= N;++j)
update(a[i].id * j,(long long)a[i].a * mu[j]);
}
else
{
if(a[i].n > a[i].m)
swap(a[i].n,a[i].m);
for(register int l = 1,r;l <= a[i].n;l = r + 1)
{
r = min(a[i].n / (a[i].n / l),a[i].m / (a[i].m / l));
ans[a[i].id] += (query(r) - query(l - 1)) * (a[i].n / l) * (a[i].m / l);
}
if(++tot == q)
break;
}
for(register int i = 1;i <= q;++i)
printf("%lld\n",ans[i] & (1LL << 31) - 1);
}