题目大意：
当
1≤i≤n,1≤j≤m
时
gcd(i,j)
的因数之和中不大于
a
的值之和，即：∑i=1n∑j=1m⎛⎝∑d|gcd(i,j)d)×⎛⎝⎛⎝∑d|gcd(i,j)d⎞⎠≤a⎞⎠⎞⎠
题解：
假设没有
a
的限制。
设f(n,m,i)为
1≤x≤n,1≤y≤m
中，
gcd(x,y)=i
的个数。
F(n,m,i)
为
1≤x≤n,1≤y≤m
中，
i|gcd(x,y)
的个数。 ∴
f(n,m,i)=∑i|dμ(di)F(n,m,d)=∑i|dμ(di)⌊nd⌋⌊md⌋
设
σ(i)
为
i
的因数之和。
∴
∑i=1min(n,m)σ(i)f(n,m,i)=∑i=1min(n,m)σ(i)∑i|dμ(di)⌊nd⌋⌊md⌋
=∑d=1min(n,m)⌊nd⌋⌊md⌋∑i|dμ(di)σ(i)
暴力处理前缀和
∑i|dμ(di)σ(i)
，即枚举i，处理i的倍数。
计算
σ(i)
也是靠暴力，枚举i，处理i的倍数（保证不超时）。
现在来考虑有a的限制。 发现只有
σ(i)≤a
才会加进去，则将询问按
a
从小到大排序，σ(i)也从小到大排序，用树状数组记录前缀和，每次将
σ(i)≤a
的
∑i|dμ(di)σ(i)
加入前缀和，就可以做了。
代码：
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=
100005,MAXQ=
20005;
typedef pair<
int,
int> sigma;
struct Query
{
int n,m,a,id;
bool operator < (
const Query &t)
const
{
return a<t.a;
}
};
struct tsum
{
int s[MAXN];
void add(
int val,
int id)
{
for(
int i=id;i<MAXN;i+=(i&(-i)))
s[i]+=val;
}
int get(
int id)
{
int ret=
0;
for(
int i=id;i>
0;i-=(i&(-i)))
ret+=s[i];
return ret;
}
};
Query que[MAXQ];
int ans[MAXQ];
sigma si[MAXN];
int mu[MAXN],prime[MAXN/
3],pcnt;
bool noprime[MAXN];
tsum fu;
void Init();
int main()
{
Init();
int Q;
scanf(
"%d",&Q);
for(
int i=
1;i<=Q;i++)
{
scanf(
"%d%d%d",&que[i].n,&que[i].m,&que[i].a);
que[i].id=i;
}
sort(que+
1,que+Q+
1);
int lasta=
0;
for(
int i=
1;i<=Q;i++)
{
for(
int j=lasta+
1;si[j].first<=que[i].a;j++)
{
for(
int k=
1;k*si[j].second<MAXN;k++)
fu.add(si[j].first*mu[k],k*si[j].second);
lasta=j;
}
if(que[i].n>que[i].m)
swap(que[i].n,que[i].m);
int last=
0;
for(
int d=
1;d<=que[i].n;d=last+
1)
{
last=min(que[i].n/(que[i].n/d),que[i].m/(que[i].m/d));
ans[que[i].id]+=(que[i].n/d)*(que[i].m/d)*(fu.get(last)-fu.get(d-
1));
}
ans[que[i].id]&=
0x7FFFFFFF;
}
for(
int i=
1;i<=Q;i++)
printf(
"%d\n",ans[i]);
return 0;
}
void Init()
{
noprime[
1]=
1;
mu[
1]=
1;
for(
int i=
1;i<MAXN;i++)
{
if(!noprime[i])
{
prime[++pcnt]=i;
mu[i]=-
1;
}
for(
int j=
1;j<=pcnt&&i*prime[j]<MAXN;j++)
{
noprime[i*prime[j]]=
1;
if(i%prime[j]==
0)
break;
mu[i*prime[j]]=-mu[i];
}
}
for(
int i=
1;i<MAXN;i++)
for(
int j=i;j<MAXN;j+=i)
si[j].first+=i;
for(
int i=
1;i<MAXN;i++)
si[i].second=i;
sort(si+
1,si+MAXN);
}
