题目
题目描述
设d(x)为x的约数个数，给定N、M，求 $\sum^N_{i=1}\sum^M_{j=1}d(ij)$
输入输出格式
输入格式：
输入文件包含多组测试数据。第一行，一个整数T，表示测试数据的组数。接下来的T行，每行两个整数N、M。
输出格式：
T行，每行一个整数，表示你所求的答案。
输入输出样例
输入样例#1：
2
7 4
5 6
输出样例#1：
110
121
说明
1<=N, M<=50000
1<=T<=50000
题解
首先有个公式$d(ij)=\sum_{x\vert i}\sum_{y\vert j}[\gcd(x,y)==1]$
如果没有$\gcd(x,y)$的限制，这个就是$i$的约数个数与$j$的约数个数的乘积了，这样肯定会用重复的部分
设一个约数为$x\times \frac{j}{y}$，相当于从$i$中取出一个$x$，从$j$中去掉一个$y$进行组合
如果$x,y$有公因子$d$，$d$从$x$取出又从$y$中去掉了，所以相当于$\frac{x}{d}\times \frac{jd}{y}$
有了这个公式就可以化式子了
即$\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{x\vert i}\sum_{y\vert j}[\gcd(x,y)==1]$ $=\sum_{i=1}^{n}\sum_{j=1}^{m}\left\lfloor\frac{n}{i}\right\rfloor\left\lfloor\frac{m}{j}\right\rfloor[\gcd(i,j)==1]$
设$F(x)=\sum_{x\vert d}f(d),f(d)=\sum_{i=1}^{n}\sum_{j=1}^{m}\left\lfloor\frac{n}{i}\right\rfloor\left\lfloor\frac{m}{j}\right\rfloor[\gcd(i,j)==d]$
则有$F(x)=\sum_{i=1}^{n}\sum_{j=1}^{m}\left\lfloor\frac{n}{i}\right\rfloor\left\lfloor\frac{m}{j}\right\rfloor[x\vert \gcd(i,j)]=\sum_{i=1}^{\left\lfloor\frac{m}{x}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{n}{x}\right\rfloor}\left\lfloor\frac{n}{ix}\right\rfloor\left\lfloor\frac{m}{jx}\right\rfloor$
所以$f(x)=\sum_{x\vert d}\mu(\frac{d}{x})F(d)$
$f(1)=\sum_{x=1}^{min(n,m)}\mu(x)\sum_{i=1}^{\left\lfloor\frac{n}{x}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{x}\right\rfloor}\left\lfloor\frac{n}{ix}\right\rfloor\left\lfloor\frac{m}{jx}\right\rfloor$
后面的部分可以处理出来$\sum_{i=1}^{n}\left\lfloor\frac{n}{i}\right\rfloor$的值就可以$O(1)$算了
怎么处理？先整除分块$O(n\sqrt n)$预处理就好~
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<algorithm>
# define LL long long
using namespace std;
const int MAX=5e4+5;
struct p{
int n,m;
}qu[MAX];
int T,n,m,N,tot;
LL ans;
int pm[MAX],u[MAX],sum[MAX];
LL _sum[MAX];
bool use[MAX];
void ss(int n)
{
u[1]=sum[1]=1,_sum[1]=1;
for(int i=2;i<=n;++i)
{
if(!use[i]) pm[++tot]=i,u[i]=-1;
for(int j=1;j<=tot&&pm[j]*i<=n;++j)
{
use[pm[j]*i]=1;
if(i%pm[j]==0) break;
u[pm[j]*i]=-u[i];
}
sum[i]=sum[i-1]+u[i];
for(int l=1,r,_N;l<=i;l=r+1)
_N=i/l,r=i/_N,_sum[i]+=1ll*(r-l+1)*_N;
}
}
int main()
{
scanf("%d",&T);
for(int i=1;i<=T;++i)
{
scanf("%d%d",&qu[i].n,&qu[i].m);
if(qu[i].n>qu[i].m) swap(qu[i].n,qu[i].m);
N=max(N,qu[i].m);
}
ss(N);
for(int t=1;t<=T;++t)
{
ans=0;
for(int l=1,r,_N,_M;l<=qu[t].n;l=r+1)
_N=qu[t].n/l,_M=qu[t].m/l,r=min(qu[t].n/_N,qu[t].m/_M),ans+=(sum[r]-sum[l-1])*_sum[_N]*_sum[_M];
printf("%lld\n",ans);
}
return 0;
}
