题目
题目描述
有一张N*m的数表，其第i行第j列（1 < =i < =n，1 < =j < =m）的数值为能同时整除i和j的所有自然数之和。给定a，计算数表中不大于a的数之和。
输入输出格式
输入格式：
输入包含多组数据。
输入的第一行一个整数Q表示测试点内的数据组数
接下来Q行，每行三个整数n，m，a(10^-9<= a <=10^9)描述一组数据。
输出格式：
对每组数据，输出一行一个整数，表示答案模2^31的值。
输入输出样例
输入样例#1：
2
4 4 3
10 10 5
输出样例#1：
20
148
说明
1 < =N．m < =10^5 ， 1 < =Q < =2*10^4
题解
先不管$a$的限制，题目要求：$\sum_{i=1}^{n}\sum_{j=1}^{m}\sigma (\gcd(i,j))$
化一下：$\sum_{x=1}^{min(n,m)}\sigma(x) \sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)==x]$
发现后半部分很莫比乌斯，反演一下：$\sum_{x=1}^{min(n,m)}\sigma(x)\sum_{x\vert d}\mu(\frac{d}{x})\left\lfloor\frac{n}{d}\right\rfloor\left\lfloor\frac{m}{d}\right\rfloor$
则有：$\sum_{d=1}^{min(n,m)}\left\lfloor\frac{n}{d}\right\rfloor\left\lfloor\frac{m}{d}\right\rfloor\sum_{x\vert d}\sigma(x)\mu(\frac{d}{x})$
这样就可以搞了，但是有$a$的限制怎么办呢？
离线处理询问，按照$a$的大小排序，$\sigma$也按大小排序
这样每次的询问把小于询问的$\sigma$加进去，整除分块就行了
修改和查询用数据结构搞，树状数组就可以
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
using namespace std;
const int MAX=1e5+1,mod=(1<<31);
struct p{
int x,id;
bool operator< (const p &a)
const{
return x<a.x;
}
}d[MAX];
struct q{
int n,m,a,id;
bool operator< (const q &b)
const{
return a<b.a;
}
}qu[MAX];
int t,maxn,tot;
int s[MAX],ans[MAX],u[MAX],pm[MAX],p1[MAX],p2[MAX];
bool use[MAX];
int lowbit(int x)
{
return x&-x;
}
void change(int x,int dis)
{
for(int i=x;i<=maxn;i+=lowbit(i))
s[i]+=dis;
}
int ask(int x)
{
int ans=0;
for(int i=x;i;i-=lowbit(i))
ans+=s[i];
return ans;
}
int main()
{
scanf("%d",&t);
for(int i=1;i<=t;++i)
scanf("%d%d%d",&qu[i].n,&qu[i].m,&qu[i].a),qu[i].id=i,maxn=max(maxn,min(qu[i].n,qu[i].m));
u[1]=1,d[1].x=d[1].id=1;
for(int i=2;i<=maxn;++i)
{
d[i].id=i;
if(!use[i]) pm[++tot]=i,u[i]=-1,d[i].x=p1[i]=i+1,p2[i]=i;
for(int j=1;j<=tot&&pm[j]*i<=maxn;++j)
{
use[i*pm[j]]=1;
if(i%pm[j]==0) u[i*pm[j]]=0,p2[i*pm[j]]=p2[i]*pm[j],p1[i*pm[j]]=p1[i]+p2[i*pm[j]],d[i*pm[j]].x=d[i].x/p1[i]*p1[i*pm[j]];
else u[i*pm[j]]=-u[i],p1[i*pm[j]]=pm[j]+1,p2[i*pm[j]]=pm[j],d[i*pm[j]].x=d[i].x*d[pm[j]].x;
}
}
sort(qu+1,qu+1+t),sort(d+1,d+1+maxn);
int pos=1;
for(int i=1;i<=t;++i)
{
if(qu[i].n>qu[i].m) swap(qu[i].n,qu[i].m);
for(;pos<=maxn&&d[pos].x<=qu[i].a;++pos)
for(int j=1;j*d[pos].id<=maxn;++j)
if(u[j]) change(d[pos].id*j,d[pos].x*u[j]);
int last=0;
for(int l=1,r;l<=qu[i].n;l=r+1)
{
int N=qu[i].n/l,M=qu[i].m/l,tt;
r=min(qu[i].n/N,qu[i].m/M),tt=ask(r),ans[qu[i].id]+=1ll*N*M*(tt-last)%mod,last=tt;
}
}
for(int i=1;i<=t;++i)
printf("%d\n",ans[i]>=0?ans[i]:ans[i]+mod);
return 0;
}
