[文章目录]
Description
对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) = k，gcd(x,y)函数为x和y的最大公约数,1≤n≤50000，1≤a≤b≤50000，1≤c≤d≤50000，1≤k≤50000
莫比乌斯反演。首先想到可以是前缀和容斥一下得到。然后考虑化简式子：∑i=1a ∑j=1b [gcd(i,j)==k]
=>等价于找k的倍数中gcd为1的：∑i=1a/k ∑j=1b/k [gcd(i,j)==1]
=>令A=a/k,B=b/k.:∑i=1A ∑j=1B [gcd(i,j)==1]
=>因为∑d|nμ(d)= 1 (n==1) || 0 (n!=1): ∑i=1A ∑j=1B ∑d|gcd(i,j) μ(d)
=>再考虑每个μ(d)对答案的贡献，不妨令B<=A : ∑i=1B*μ(i)*⌊A/i⌋*⌊B/i⌋。
其中⌊A/i⌋为1~A中i的倍数的个数，由于i为gcd(1~A,1~B)的约数，所以二者i的倍数的子集合个数乘积就为累计次数。
由于⌊A/i⌋中大部分树都是相同的，所以可以进行分块。A和B都分成√A+√B级别。所以总时间为2*√a的级别。加上预处理mu的前缀和，就能够O(maxa+T√maxa)出解了
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int mu[51000],pri[51000],cnt;
bool v[51000];
void quick_mu()
{
mu[1]=1;
for(int i=2;i<=50000;i++)
{
if(!v[i]) pri[++cnt]=i,mu[i]=-1;
for(int j=1;j<=cnt&&i*pri[j]<=50000;j++)
{
v[i*pri[j]]=1;
if(i%pri[j]==0)
{
mu[i*pri[j]]=0;
break;
}
else mu[i*pri[j]]=mu[i]*-1;
}
}
for(int i=1;i<=50000;i++)
mu[i]+=mu[i-1];
}
int work(int x,int y)
{
if(x>y) swap(x,y);
int b=1,e,re=0;
while(b<=x)
{
e=min(min(y/(y/b),x/(x/b)),x);
re+=(mu[e]-mu[b-1])*(x/b)*(y/b);
b=e+1;
}
return re;
}
int main()
{
int T,a,b,c,d,k;
scanf("%d",&T);
quick_mu();
while(T--)
{
scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
c--; a--; a/=k;b/=k;c/=k;d/=k;
printf("%d\n",work(b,d)-work(b,c)-work(a,d)+work(a,c));
}
return 0;
}