题目：
BZOJ3529
.
题目大意：设
f
(
i
,
j
)
=
∑
d
∣
g
c
d
(
i
,
j
)
d
f(i,j)=\sum_{d|gcd(i,j)}d
f
(
i
,
j
)
=
∑
d
∣
g
c
d
(
i
,
j
)
d
，给定
Q
Q
Q
组询问，每次询问
n
,
m
,
a
n,m,a
n
,
m
,
a
，求
∑
i
=
1
n
∑
j
=
1
,
f
(
i
,
j
)
≤
a
m
f
(
i
,
j
)
\sum_{i=1}^{n}\sum_{j=1,f(i,j)\leq a}^{m}f(i,j)
∑
i
=
1
n
∑
j
=
1
,
f
(
i
,
j
)
≤
a
m
f
(
i
,
j
)
.
1
≤
n
,
m
≤
1
0
5
,
1
≤
q
≤
2
∗
1
0
4
,
1
≤
∣
a
∣
≤
1
0
9
1\leq n,m\leq 10^5,1\leq q\leq 2*10^4,1\leq |a|\leq 10^9
1
≤
n
,
m
≤
1
0
5
,
1
≤
q
≤
2
∗
1
0
4
,
1
≤
∣
a
∣
≤
1
0
9
.
先考虑没有
a
a
a
限制的情况，那么：
∑
i
=
1
n
∑
j
=
1
m
f
(
i
,
j
)
=
∑
i
=
1
n
∑
j
=
1
m
∑
d
∣
g
c
d
(
i
,
j
)
d
=
∑
d
=
1
m
i
n
(
n
,
m
)
(
∑
t
∣
d
t
)
(
∑
i
=
1
n
∑
j
=
1
m
[
g
c
d
(
i
,
j
)
=
d
]
)
\sum_{i=1}^{n}\sum_{j=1}^{m}f(i,j)\\ =\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d|gcd(i,j)}d\\ =\sum_{d=1}^{min(n,m)}(\sum_{t|d}t)(\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=d])
i
=
1
∑
n
j
=
1
∑
m
f
(
i
,
j
)
=
i
=
1
∑
n
j
=
1
∑
m
d
∣
g
c
d
(
i
,
j
)
∑
d
=
d
=
1
∑
m
i
n
(
n
,
m
)
(
t
∣
d
∑
t
)
(
i
=
1
∑
n
j
=
1
∑
m
[
g
c
d
(
i
,
j
)
=
d
]
)
设
σ
(
n
)
=
∑
d
∣
n
d
\sigma(n)=\sum_{d|n}d
σ
(
n
)
=
∑
d
∣
n
d
，那么：
∑
d
=
1
m
i
n
(
n
,
m
)
(
∑
t
∣
d
t
)
(
∑
i
=
1
n
∑
j
=
1
m
[
g
c
d
(
i
,
j
)
=
d
]
)
=
∑
d
=
1
m
i
n
(
n
,
m
)
σ
(
d
)
∑
i
=
1
n
∑
j
=
1
m
[
g
c
d
(
i
,
j
)
=
d
]
=
∑
d
=
1
m
i
n
(
n
,
m
)
σ
(
d
)
∑
i
=
1
⌊
n
d
⌋
∑
j
=
1
⌊
m
d
⌋
[
g
c
d
(
i
,
j
)
=
1
]
=
∑
d
=
1
m
i
n
(
n
,
m
)
σ
(
d
)
∑
i
=
1
⌊
n
d
⌋
∑
j
=
1
⌊
m
d
⌋
∑
t
∣
i
∧
t
∣
j
μ
(
t
)
=
∑
d
=
1
m
i
n
(
n
,
m
)
σ
(
d
)
∑
t
=
1
⌊
m
i
n
(
n
,
m
)
d
⌋
μ
(
t
)
⌊
n
d
t
⌋
⌊
m
d
t
⌋
\sum_{d=1}^{min(n,m)}(\sum_{t|d}t)(\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=d])\\ =\sum_{d=1}^{min(n,m)}\sigma(d)\sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)=d]\\ =\sum_{d=1}^{min(n,m)}\sigma(d)\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{d}\right\rfloor}[gcd(i,j)=1]\\ =\sum_{d=1}^{min(n,m)}\sigma(d)\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{d}\right\rfloor}\sum_{t|i\wedge t|j}\mu(t)\\ =\sum_{d=1}^{min(n,m)}\sigma(d)\sum_{t=1}^{\left\lfloor\frac{min(n,m)}{d}\right\rfloor}\mu(t)\left\lfloor\frac{n}{dt}\right\rfloor\left\lfloor\frac{m}{dt}\right\rfloor
d
=
1
∑
m
i
n
(
n
,
m
)
(
t
∣
d
∑
t
)
(
i
=
1
∑
n
j
=
1
∑
m
[
g
c
d
(
i
,
j
)
=
d
]
)
=
d
=
1
∑
m
i
n
(
n
,
m
)
σ
(
d
)
i
=
1
∑
n
j
=
1
∑
m
[
g
c
d
(
i
,
j
)
=
d
]
=
d
=
1
∑
m
i
n
(
n
,
m
)
σ
(
d
)
i
=
1
∑
⌊
d
n
⌋
j
=
1
∑
⌊
d
m
⌋
[
g
c
d
(
i
,
j
)
=
1
]
=
d
=
1
∑
m
i
n
(
n
,
m
)
σ
(
d
)
i
=
1
∑
⌊
d
n
⌋
j
=
1
∑
⌊
d
m
⌋
t
∣
i
∧
t
∣
j
∑
μ
(
t
)
=
d
=
1
∑
m
i
n
(
n
,
m
)
σ
(
d
)
t
=
1
∑
⌊
d
m
i
n
(
n
,
m
)
⌋
μ
(
t
)
⌊
d
t
n
⌋
⌊
d
t
m
⌋
考虑枚举
c
=
d
t
c=dt
c
=
d
t
，那么：
=
∑
d
=
1
m
i
n
(
n
,
m
)
σ
(
d
)
∑
t
=
1
⌊
m
i
n
(
n
,
m
)
d
⌋
μ
(
t
)
⌊
n
d
t
⌋
⌊
m
d
t
⌋
=
∑
c
=
1
m
i
n
(
n
,
m
)
⌊
n
c
⌋
⌊
m
c
⌋
∑
d
∣
c
μ
(
c
d
)
σ
(
d
)
=\sum_{d=1}^{min(n,m)}\sigma(d)\sum_{t=1}^{\left\lfloor\frac{min(n,m)}{d}\right\rfloor}\mu(t)\left\lfloor\frac{n}{dt}\right\rfloor\left\lfloor\frac{m}{dt}\right\rfloor\\ =\sum_{c=1}^{min(n,m)}\left\lfloor\frac{n}{c}\right\rfloor\left\lfloor\frac{m}{c}\right\rfloor\sum_{d|c}\mu(\frac{c}{d})\sigma(d)
=
d
=
1
∑
m
i
n
(
n
,
m
)
σ
(
d
)
t
=
1
∑
⌊
d
m
i
n
(
n
,
m
)
⌋
μ
(
t
)
⌊
d
t
n
⌋
⌊
d
t
m
⌋
=
c
=
1
∑
m
i
n
(
n
,
m
)
⌊
c
n
⌋
⌊
c
m
⌋
d
∣
c
∑
μ
(
d
c
)
σ
(
d
)
线性筛出
μ
\mu
μ
和
σ
\sigma
σ
并预处理出它们的dirichlet卷积的前缀和
g
g
g
，然后除法分块处理即可做到
O
(
n
)
O(\sqrt{n})
O
(
n
)
处理一次询问.
考虑离线处理
a
a
a
的限制.我们先对询问按照
a
a
a
排序，把所有
d
d
d
按照
σ
(
d
)
\sigma(d)
σ
(
d
)
大小排序，并用树状数组动态维护
g
g
g
，即可做到
O
(
n
log
2
n
+
Q
n
log
n
)
O(n\log^2n+Q\sqrt{n}\log n)
O
(
n
lo
g
2
n
+
Q
n
lo
g
n
)
.
具体来说，每次当我们要加入一个数
d
d
d
的贡献时，我们枚举
d
d
d
的倍数，把这些倍数加上
d
d
d
的贡献.查询时用树状数组维护前缀和即可.
代码如下：
#include<bits/stdc++.h>
using namespace std;
#define Abigail inline void
typedef long long LL;
const int N=100000,Q=20000;
const LL mod=(1LL<<31)-1;
int tp,pr[N+9],b[N+9];
LL mu[N+9],sigma[N+9],sd[N+9];
void sieve(int n){ //先把约数和函数筛错，重写一遍后再把Mobius函数筛错的我是不是没了...
for (int i=2;i<=n;++i) b[i]=1;
sigma[1]=mu[1]=1;int v;
for (int i=2;i<=n;++i){
if (b[i]) pr[++tp]=i,mu[i]=-1,sigma[i]=sd[i]=i+1;
for (int j=1;j<=tp&&i*pr[j]<=n;++j){
b[v=i*pr[j]]=0;
if (i%pr[j]==0){
mu[v]=0;
sd[v]=sd[i]*pr[j]+1;sigma[v]=sigma[i]/sd[i]*sd[v];
break;
}
mu[v]=-mu[i];
sd[v]=pr[j]+1;sigma[v]=sigma[i]*sigma[pr[j]];
}
}
}
int t;
struct Question{
int n,m,id;
LL a;
}q[Q+9];
LL ans[Q+9];
bool cmp1(const Question &a,const Question &b){return a.a<b.a;}
int d[N+9];
bool cmp2(const int &a,const int &b){return sigma[a]<sigma[b];}
LL g[N+9];
void Bit_add(int x,LL v){for (;x<=N;x+=x&-x) g[x]+=v;}
LL Bit_query(int x){LL sum=0;for (;x;x-=x&-x) sum+=g[x];return sum;}
LL Bit_query(int x,int y){return Bit_query(y)-Bit_query(x-1);}
void solve_add(int x){
for (int i=1;i*x<=N;++i)
Bit_add(i*x,sigma[x]*mu[i]);
}
LL solve_query(int n,int m){
LL ans=0;
if (n>m) swap(n,m);
for (int l=1,r;l<=n;l=r+1){
r=min(n/(n/l),m/(m/l));
ans+=(n/l)*(m/l)*Bit_query(l,r);
}
return ans;
}
Abigail into(){
scanf("%d",&t);
for (int i=1;i<=t;++i){
scanf("%d%d%lld",&q[i].n,&q[i].m,&q[i].a);
q[i].id=i;
}
}
Abigail work(){
sieve(N);
sort(q+1,q+1+t,cmp1);
for (int i=1;i<=N;++i) d[i]=i;
sort(d+1,d+1+N,cmp2);
int now=0;
for (int i=1;i<=t;++i){
while (now<N&&sigma[d[now+1]]<=q[i].a) solve_add(d[++now]);
ans[q[i].id]=solve_query(q[i].n,q[i].m);
}
}
Abigail outo(){
for (int i=1;i<=t;++i)
printf("%lld\n",ans[i]&mod);
}
int main(){
into();
work();
outo();
return 0;
}