【BZOJ 2301】 [HAOI2011]Problem b

2301: [HAOI2011]Problem bTime Limit:50 SecMemory Limit:256 MBSubmit:1501Solved:628[Submit][Status]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

22 5 1 5 11 5 1 5 2

Sample Output

143

HINT

100%的数据满足：1≤n≤50000，1≤a≤b≤50000，1≤c≤d≤50000，1≤k≤50000

莫比乌斯函数。

与【BZOJ 1101】基本一样，只是比他多了个下限，只要把多余部分减去，多减掉的加上即可（类似容斥原理）

#include <iostream>#include <cmath>#include <algorithm>#include <cstdio>#include <cstdlib>#include <cstring>#define LL long longusing namespace std;int check[50005],mu[50005],p[50005],sum[50005];void Getmobius(){memset(check,0,sizeof(check));mu[1]=1;int tot=0;for (int i=2;i<=50000;i++){if (!check[i]){p[++tot]=i;mu[i]=-1;}for (int j=1;j<=tot;j++){if (i*p[j]>50000) break;check[i*p[j]]=1;if (i%p[j]==0){mu[i*p[j]]=0;break;}else mu[i*p[j]]=-mu[i];}}sum[0]=0;for (int i=1;i<=50000;i++)sum[i]=sum[i-1]+mu[i];}LL Calc(int a,int b){LL ans=0LL;int pos;for (int d=1;d<=min(a,b);d=pos+1){pos=min(a/(a/d),b/(b/d));ans+=(LL)(sum[pos]-sum[d-1])*(a/d)*(b/d);}return ans;}int main(){Getmobius();int T;scanf("%d",&T);while (T–){int a,b,c,d,k;scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);a=(a-1)/k,b/=k,c=(c-1)/k,d/=k;LL ans=0LL;ans=Calc(b,d)-Calc(a,d)-Calc(c,b)+Calc(a,c);printf("%lld\n",ans);}return 0;}

感悟了不同的人生。凌晨，随着滑轮接触地面，