题目描述
有一张N*m的数表，其第i行第j列（1 < =i < =礼，1 < =j < =m）的数值为能同时整除i和j的所有自然数之和。给定a，计算数表中不大于a的数之和。
输入输出格式
输入格式：
输入包含多组数据。 输入的第一行一个整数Q表示测试点内的数据组数，接下来Q行，每行三个整数n，m，a(|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
题解：
令F[i]为i的因数和,g[i]为gcd=i的数量
则ans=∑∑F[gcd(i,j)]
=∑dF[d]g[d]
g[d]=∑i∑j[gcd(i,j)==d] (i<=n,j<=m)
=∑∑[gcd(i,j)==1] (i<=n/d,j<=m/d)
=∑∑∑pμ(p) (p|i,p|j)
=∑pμ(p)∑∑1 (p<=n/d,i<=n/dp,j<=m/dp)
=∑pμ(p)[n/dp][m/dp]
ans=∑dF[d]∑pμ(p)[n/dp][m/dp]
令k=dp
g[d]=∑k[n/k][m/k]μ(k/d) (k<=n，d|k)
ans=∑k[n/k][m/k]∑dF[d]μ(k/d) (d|k)
令f[k]=∑dF[d]μ(k/d) (d|k)
处理处f的前缀和就行了，对于每个F[i],把它的f[x*i]全部加上F[i]*mu[x]
至于小于a的条件，离线按a排序，将F按从小到大顺序加入维护
分块就不说了
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
struct data
{
int id,n,m,a;
}a[];
int Mod=(<<);
int f[],mu[],ms[],prime[],tot;
int c[],p[],now=,ans[];
bool vis[];
bool cmp2(data a,data b)
{
return a.a<b.a;
}
bool cmp(int a,int b)
{
return f[a]<f[b];
}
void mobius()
{int i,j;
mu[]=;
ms[]=;f[]=;
for (i=;i<=;i++)
{
if (vis[i]==)
{
mu[i]=-;
f[i]=i+;
ms[i]=i;
prime[++tot]=i;
}
for (j=;j<=tot,prime[j]*i<=;j++)
{
vis[i*prime[j]]=;
if (i%prime[j])
{
ms[i*prime[j]]=prime[j];
f[prime[j]*i]=f[i]*f[prime[j]];
mu[i*prime[j]]=-mu[i];
}
else
{
ms[prime[j]*i]=ms[i]*prime[j];
if (ms[i]==i) f[prime[j]*i]=(ms[prime[j]*i]*prime[j]-)/(prime[j]-);
else f[prime[j]*i]=f[i/ms[i]]*f[prime[j]*ms[i]];
mu[i*prime[j]]=;
break;
}
}
}
}
void add(int x,int d)
{
while (x<=)
{
c[x]+=d;
x+=(x&(-x));
}
}
int query(int x)
{
int s=;
while (x)
{
s+=c[x];
x-=(x&(-x));
}
return s;
}
void solve(int x)
{int j,pos,i,lasts,ss;
for (;f[p[now]]<=a[x].a;now++)
{
for (j=;p[now]*j<=;j++)
add(p[now]*j,f[p[now]]*mu[j]);
}
pos=;
lasts=;
for (i=;i<=a[x].n;i=pos+)
{
pos=min(a[x].n/(a[x].n/i),a[x].m/(a[x].m/i));
ss=query(pos);
ans[a[x].id]=(ans[a[x].id]+(a[x].n/i)*(a[x].m/i)*(ss-lasts));
//cout<<ans[a[x].id]<<' ';
lasts=ss;
}
while (ans[a[x].id]<) ans[a[x].id]+=Mod;
//cout<<endl;
}
int main()
{int T,i,j;
cin>>T;
for (i=;i<=T;i++)
{
scanf("%d%d%d",&a[i].n,&a[i].m,&a[i].a);
if (a[i].n>a[i].m) swap(a[i].n,a[i].m);
a[i].id=i;
}
mobius();
for (i=;i<=;i++) p[i]=i;
sort(p+,p+,cmp);
sort(a+,a+T+,cmp2);
for (i=;i<=T;i++)
solve(i);
for (i=;i<=T;i++)
printf("%d\n",ans[i]);
}