Mission

对于给出的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

Solution

裸的莫比乌斯反演。 把询问拆分成四个子询问，然后莫比乌斯反演要用分块求解。

Code

#include<iostream> #include<algorithm> #include<stdio.h> #include<math.h> #include<string.h> #define ll long long using namespace std; const char* fin="ex2301.in"; const char* fout="ex2301.out"; const ll inf=0x7fffffff; const ll maxn=50007; ll t,a,b,c,d,ind,i,j,k; ll miu[maxn],p[maxn]; bool bz[maxn]; ll ans; ll f(ll n,ll m){ ll i,j,k,ans=0; if (n<=0 || m<=0) return 0; if (n>m) swap(n,m); for (i=1;ind*i<=n;){ j=min(n/(ind*(n/(ind*i))),m/(ind*m/(ind*i))); ans+=(n/(ind*i))*(m/(ind*i))*(miu[j]-miu[i-1]); i=j+1; } return ans; } int main(){ freopen(fin,"r",stdin); freopen(fout,"w",stdout); scanf("%lld",&t); miu[1]=1; for (i=2;i<maxn;i++){ if (!bz[i]){ p[++p[0]]=i; miu[i]=-1; } for (j=1;j<=p[0];j++){ k=i*p[j]; if (k>=maxn) break; bz[k]=true; if (i%p[j]==0){ miu[k]=0; break; }else miu[k]=-miu[i]; } } for (i=1;i<maxn;i++) miu[i]+=miu[i-1]; while (t--){ scanf("%lld%lld%lld%lld%lld",&a,&b,&c,&d,&ind); printf("%lld\n",f(b,d)-f(b,c-1)-f(a-1,d)+f(a-1,c-1)); } return 0; }