题解 P3455 【[POI2007]ZAP-Queries】
我顺便来安利一下自己的博客peng-ym's blog里面也有莫比乌斯反演与整除分块的介绍，不知道的可以看一看哦！
题目大意
- 求
\sum_{i=1}^{a}\sum_{j=1}^{b}[gcd(x,y)=d] - 多组输入
-
1\le d\le a,b\le 50000
解题思路
- 根据之前做过的题的经验(YY的GCD)，那么这一题就显得十分套路
(简单)了。 - 我们设：
f(k)=\sum_{i=1}^{a}\sum_{j=1}^{b}[gcd(i,j)=k] F(n)=\sum_{n|k}f(k)=\lfloor\frac{a}{n}\rfloor\lfloor\frac{b}{n}\rfloor 则可以由莫比乌斯反演可以推出：
f(n)=\sum_{n|k}\mu(\lfloor\frac{k}{n}\rfloor)F(k) - (PS:如果不知道为什么要设这两个函数，可以点开我上面放的链接)
- 设完这两个函数之后，我们便惊喜的发现，
Ans=f(d) - 于是就直接开始推答案：
Ans=\sum_{d|k}\mu(\lfloor\frac{k}{d}\rfloor)F(k) 枚举
\lfloor\frac{k}{d}\rfloor 设为t Ans=\sum_{t=1}^{min(a,b)}\mu(t)\lfloor\frac{a}{td}\rfloor\lfloor\frac{b}{td}\rfloor 这时候，这个式子已经可以做到
O(n) 的时间复杂度了，但是因为有多组数据，所以我们再用一下整除分块，这题就可以做到O(\sqrt{n}) 了。 - 下附代码：
#include<bits/stdc++.h>
#define N 60010
using namespace std;
inline void read(long long &x)
{
x=0;
static long long p;p=1;
static char c;c=getchar();
while(!isdigit(c)){if(c=='-')p=-1;c=getchar();}
while(isdigit(c)) {x=(x<<1)+(x<<3)+(c-48);c=getchar();}
x*=p;
}
bool vis[N];
long long prim[N],mu[N],sum[N],cnt;
void get_mu(long long n)
{
mu[1]=1;
for(long long i=2;i<=n;i++)
{
if(!vis[i]){mu[i]=-1;prim[++cnt]=i;}
for(long long j=1;j<=cnt&&i*prim[j]<=n;j++)
{
vis[i*prim[j]]=1;
if(i%prim[j]==0)break;
else mu[i*prim[j]]=-mu[i];
}
}
for(long long i=1;i<=n;i++)sum[i]=sum[i-1]+mu[i];
}
int main()
{
// freopen("P3455.in","r",stdin);
// freopen("P3455.out","w",stdout);
long long t;
read(t);
get_mu(50000);
while(t--)
{
static long long a,b,d;
read(a);read(b);read(d);
static long long max_rep,ans;
max_rep=min(a,b);ans=0;
for(long long l=1,r;l<=max_rep;l=r+1)
{
r=min(a/(a/l),b/(b/l));
ans+=(a/(l*d))*(b/(l*d))*(sum[r]-sum[l-1]);
}
printf("%lld\n",ans);
}
return 0;
}