BZOJ2301: [HAOI2011]Problem b(莫比烏斯反演)

Description

對于給出的n個詢問，每次求有多少個數對(x,y)，滿足a≤x≤b，c≤y≤d，且gcd(x,y) = k，gcd(x,y)函數為x和y的最大公約數。

Input

第一行一個整數n，接下來n行每行五個整數，分別表示a、b、c、d、k

Output

共n行，每行一個整數表示滿足要求的數對(x,y)的個數?

Sample Input

2
2 5 1 5 1
1 5 1 5 2

Sample Output

14
3

解題思路：

和1101一樣，最后二維容斥一下就好了。

代碼：

#include<cstdio>
#include<cstring>
#include<algorithm>
typedef long long lnt;
const int N=50010;
int prime[N];
int miu[N];
lnt s[N];
bool vis[N];
int cnt;
int T;
void gtp(void)
{miu[1]=1;for(int i=2;i<N;i++){if(!vis[i]){prime[++cnt]=i;miu[i]=-1;}for(int j=1;j<=cnt&&prime[j]*i<N;j++){vis[prime[j]*i]=true;if(i%prime[j]==0){miu[i*prime[j]]=0;break;}miu[prime[j]*i]=-miu[i];}}for(int i=1;i<N;i++)s[i]=s[i-1]+miu[i];return ;
}
lnt query(lnt a,lnt b,lnt d)
{a/=d;b/=d;lnt c=std::min(a,b);lnt ans=0;for(int k=1,u;k<=c;k=u+1){u=std::min(a/(a/k),b/(b/k));ans+=(s[u]-s[k-1])*(a/k)*(b/k);}return ans;
}
int main()
{gtp();scanf("%d",&T);while(T--){lnt a,b,c,d,k;scanf("%lld%lld%lld%lld%lld",&a,&b,&c,&d,&k);a--,c--;lnt ans=query(b,d,k)+query(a,c,k)-query(a,d,k)-query(b,c,k);printf("%lld\n",ans);}return 0;
}

?