题目
对于给出的 n 个询问，每次求有多少个数对 (x,y) ，满足 a ≤ x ≤ b ， c ≤ y ≤ d ，且 gcd(x,y) = k。
分析
利用容斥原理，我们可以把问题转化为求1≤x≤n,1≤y≤m,中有多少个数对满足gcd(x,y)=k. 我们令f(i)为1<=x<=n,1<=y<=m且gcd(x,y)=i的数对(x,y)的个数，F(i)为1<=x<=n,1<=y<=m且i|gcd(x,y)的数对(x,y)的个数 显然，
F(n)=⌊nd⌋⌊md⌋
F
(
n
)
=
⌊
n
d
⌋
⌊
m
d
⌋
由于满足
F(n)=∑n|df(d)
F
(
n
)
=
∑
n
|
d
f
(
d
)
因此可以用莫比乌斯反演，
f(i)=∑i|dμ(di)F(d)=∑i|dμ(di)⌊nd⌋⌊md⌋
f
(
i
)
=
∑
i
|
d
μ
(
d
i
)
F
(
d
)
=
∑
i
|
d
μ
(
d
i
)
⌊
n
d
⌋
⌊
m
d
⌋
由于
⌊nd⌋
⌊
n
d
⌋
最多只有2
n−−√
n
个取值，则可以用分块的方法做 友情链接：http://blog.csdn.net/can919/article/details/56281309
下附代码
using namespace std;
int mobiwuzi[
50005];
int sum[
50005];
bool vis[
50005];
int prime[
50005];
void shai(){
long long cnt=
0;
mobiwuzi[
1]=
1;
for(long long i=
2;i<=
50000;i++){
if(!vis[i]){
prime[++cnt]=i;
mobiwuzi[i]=-
1;
}
for(long long j=
1;j<=cnt&&i
*prime[j]<=
50000;j++){
vis[i
*prime[j]]=
1;
if(i
%prime[j]==
0)
mobiwuzi[i
*prime[j]]=
0;
else
mobiwuzi[i
*prime[j]]=-mobiwuzi[i];
if(i
%prime[j]==
0)
break;
}
}
}
int f(
int n,
int m){
if(n>
m)
swap(n,
m);
int last,ans=
0;
for(
int i=
1;i<=n;){
last=min(n/(n/i),
m/(m/i));
ans+=(n/i)
*(m/i)
*(sum[
last]-sum[i-
1]);
i=
last+
1;
}
return ans;
}
int main()
{
shai();
for(
int i=
1;i<=
50000;i++)
sum[i]=sum[i-
1]+mobiwuzi[i];
int t;
scanf(
"%d",&t);
while(t--){
int a,b,c,d,k;
scanf(
"%d%d%d%d%d",&a,&b,&c,&d,&k);
printf(
"%d\n",f(b/k,d/k)-f((a-
1)/k,d/k)-f(b/k,(c-
1)/k)+f((a-
1)/k,(c-
1)/k));
}
}
