欢迎访问个人博客

传送门 $\looparrowright$

题目描述

  对于给出的 $n$ 个询问，每次求有多少个数对 $(x,y)$，满足 $a\le x\le b$，$c\le y\le d$，且$\gcd (x,y)=k$，$\gcd (x,y)$ 函数为 $x$ 和 $y$ 的最大公约数。

输入格式

  第一行一个整数 $n$，接下来 $n$ 行每行五个整数，分别表示 $a,b,c,d,k$。

输出格式

  共 $n$ 行，每行一个整数表示满足要求的数对 $(x,y)$ 的个数。

输入输出样例

输入 #1

2 2 5 1 5 1 1 5 1 5 2

输出 #1

14 3

说明/提示

  对于 $100\%$ 的数据满足：$1\le n,k\le 5\times 10^4$，$1\le a\le b\le 5\times 10^4$，$1\le c\le d\le 5\times 10^4$。

分析

  令二元函数 $f(x,y)=\sum _{i=1}^x\sum _{j=1}^y[\gcd (i,j)=k]$，其中 $x,y\in N^{\ast }$。由题意，所求答案为 $\sum _{i=a}^b\sum _{j=c}^d[\gcd (i,j)=k]$；依据容斥原理，$ans=f(b,d)-f(a-1,d)-f(b,c-1)+f(a-1,c-1)$。   任务转化为，对于给定的 $n,m\in N^{\ast }$，求 $f(n,m)=\sum _{i=1}^n\sum _{j=1}^m[\gcd (i,j)=k]$ 的值。   首先，$k$ 为 $i,j$ 的最大公约数，故 $\frac{i}{k}$ 与 $\frac{j}{k}$ 互质，即 $\gcd (\frac{i}{k},\frac{j}{k})=1$。所以 $f(n,m)=\sum _{i=1}^n\sum _{j=1}^m\left[\gcd \left(\frac{i}{k},\frac{j}{k}\right)=1\right]$；从此式看出，$\frac{i}{k}$ 的上限为 $\lfloor \frac{n}{k}\rfloor$，$\frac{j}{k}$ 的上限为 $\lfloor \frac{m}{k}\rfloor$；因此等价于， $f(n,m)=\sum _{i=1}^{\lfloor \frac{n}{k}\rfloor }\sum _{j=1}^{\lfloor \frac{m}{k}\rfloor }[\gcd (i,j)=1]$。   接下来利用莫比乌斯反演的性质，$\gcd (i,j)=1\iff \sum _{d\mid \gcd (i,j)}\mu (d)$。故 $f(n,m)=\sum _{i=1}^{\lfloor \frac{n}{k}\rfloor }\sum _{j=1}^{\lfloor \frac{m}{k}\rfloor }\sum _{d\mid \gcd (i,j)}\mu (d)$。   接下来变换求和次序，改为枚举 $d$。$f(n,m)=\sum _{d=1}^{\min \left(\lfloor \frac{n}{k}\rfloor ,\lfloor \frac{n}{k}\rfloor \right)}\sum _{i=1}^{\lfloor \frac{n}{k}\rfloor }\sum _{j=1}^{\lfloor \frac{m}{k}\rfloor }\mu (d)[d\mid \gcd (i,j)]$；由于 $\mu (d)$ 为只与 $d$ 相关的函数，则 $f(n,m)=\sum _{d=1}^{\min \left(\lfloor \frac{n}{k}\rfloor ,\lfloor \frac{n}{k}\rfloor \right)}\mu (d)\sum _{i=1}^{\lfloor \frac{n}{k}\rfloor }\sum _{j=1}^{\lfloor \frac{m}{k}\rfloor }[d\mid \gcd (i,j)]$。   有条件 $d\mid \gcd (i,j)$，故可设 $\gcd (i,j)=pd$；由最大公约数的定义 $pd\mid i$ 且 $pd\mid j$，因此假设 $i=p_{1}pd$，$j=p_{2}pd$；其中，$p,p_1,p_2\in N^{\ast }$。经过上述略证， $d\mid \gcd (i,j)$ 的充要条件是：$i,j$ 都为 $d$ 的倍数。在区间 $\left[1,\lfloor \frac{n}{k}\rfloor \right]$ 中，$d$ 的倍数有 $\lfloor \frac{\lfloor \frac{n}{k}\rfloor }{d}\rfloor$ 个；在区间 $\left[1,\lfloor \frac{m}{k}\rfloor \right]$ 中，$d$ 的倍数有 $\lfloor \frac{\lfloor \frac{m}{k}\rfloor }{d}\rfloor$ 个；因此，满足条件 $d\mid \gcd (i,j)$ 的数对 $(i,j)$ 的个数有 $\sum _{i=1}^{\lfloor \frac{n}{k}\rfloor }\sum _{j=1}^{\lfloor \frac{m}{k}\rfloor }[d\mid \gcd (i,j)]=\lfloor \frac{\lfloor \frac{n}{k}\rfloor }{d}\rfloor \times \lfloor \frac{\lfloor \frac{m}{k}\rfloor }{d}\rfloor$。   将 $\sum _{i=1}^{\lfloor \frac{n}{k}\rfloor }\sum _{j=1}^{\lfloor \frac{m}{k}\rfloor }[d\mid \gcd (i,j)]=\lfloor \frac{\lfloor \frac{n}{k}\rfloor }{d}\rfloor \times \lfloor \frac{\lfloor \frac{m}{k}\rfloor }{d}\rfloor$ 代入，得 $f(n,m)=\sum _{d=1}^{\min \left(\lfloor \frac{n}{k}\rfloor ,\lfloor \frac{n}{k}\rfloor \right)}\lfloor \frac{\lfloor \frac{n}{k}\rfloor }{d}\rfloor \lfloor \frac{\lfloor \frac{m}{k}\rfloor }{d}\rfloor \mu (d)$。该式可用数论分块解决。   结合以上   $\begin{array}{rl}f(n,m)& =\sum _{i=1}^n\sum _{j=1}^m[\gcd (i,j)=k]\\ & =\sum _{i=1}^n\sum _{j=1}^m\left[\gcd \left(\frac{i}{k},\frac{j}{k}\right)=1\right]\\ & =\sum _{i=1}^{\lfloor \frac{n}{k}\rfloor }\sum _{j=1}^{\lfloor \frac{m}{k}\rfloor }[\gcd (i,j)=1]\\ & =\sum _{i=1}^{\lfloor \frac{n}{k}\rfloor }\sum _{j=1}^{\lfloor \frac{m}{k}\rfloor }\sum _{d\mid \gcd (i,j)}\mu (d)\\ & =\sum _{d=1}^{\min \left(\lfloor \frac{n}{k}\rfloor ,\lfloor \frac{n}{k}\rfloor \right)}\sum _{i=1}^{\lfloor \frac{n}{k}\rfloor }\sum _{j=1}^{\lfloor \frac{m}{k}\rfloor }\mu (d)[d\mid \gcd (i,j)]\\ & =\sum _{d=1}^{\min \left(\lfloor \frac{n}{k}\rfloor ,\lfloor \frac{n}{k}\rfloor \right)}\mu (d)\sum _{i=1}^{\lfloor \frac{n}{k}\rfloor }\sum _{j=1}^{\lfloor \frac{m}{k}\rfloor }[d\mid \gcd (i,j)]\\ & =\sum _{d=1}^{\min \left(\lfloor \frac{n}{k}\rfloor ,\lfloor \frac{n}{k}\rfloor \right)}\lfloor \frac{\lfloor \frac{n}{k}\rfloor }{d}\rfloor \lfloor \frac{\lfloor \frac{m}{k}\rfloor }{d}\rfloor \mu (d)\end{array}$   综上所述，对于给定的 $n,m$ 最终用数论分块求解 $f(n,m)$ 的值 。假设在区间 $[l,r]$ 内，$\lfloor \frac{\lfloor \frac{n}{k}\rfloor }{d}\rfloor \times \lfloor \frac{\lfloor \frac{m}{k}\rfloor }{d}\rfloor$ 恒为 $A$，则 $\sum _{d=l}^r\lfloor \frac{\lfloor \frac{n}{k}\rfloor }{d}\rfloor \lfloor \frac{\lfloor \frac{m}{k}\rfloor }{d}\rfloor \mu (d)=A\sum _{d=l}^r\mu (d)$；显然，我们要预处理莫比乌斯函数的前缀和，才能在 $O(1)$ 内求出一个分块的值。   题目的最终答案为 $f(b,d)-f(a-1,d)-f(b,c-1)+f(a-1,c-1)$。

代码

#include<iostream> #include<cstring> #include<algorithm> #define ll long long #define N 50006 using namespace std; bool vis[N]; int prime[N>>1];//质数 int mu[N];//莫比乌斯函数 int sum[N];//mu[i]的前缀和 int cnt; int a,b,c,d,k; //-------------------------------------------- //欧拉筛求得莫比乌斯函数 //求莫比乌斯函数的前缀和 void init(int n) { mu[1]=1; int i,j; for(i=2;i<=n;i++) { if(!vis[i]) { prime[++cnt]=i; mu[i]=-1; } for(j=1;j<=cnt&&i*prime[j]<=n;j++) { vis[i*prime[j]]=1; if(i%prime[j]==0) { mu[i*prime[j]]=0; break; } else mu[i*prime[j]]=-mu[i]; } } for(i=1;i<=n;i++) sum[i]=sum[i-1]+mu[i]; } //-------------------------------------------- //-------------------------------------------------- //对于给定的n,m //计算f(n,m) //将n/k,m/k看作整体 inline ll f(int n,int m) { n/=k; m/=k; if(n>m) swap(n,m); int l,r; ll res=0; for(l=1;l<=n;l=r+1) { r=min(n/(n/l),m/(m/l)); res=res+1ll*(n/l)*(m/l)*(sum[r]-sum[l-1]); } return res; } //-------------------------------------------------- int main() { init(50000); int _; for(cin>>_;_;_--) { scanf("%d%d%d%d%d",&a,&b,&c,&d,&k); //容斥原理 printf("%lld\n",f(b,d)-f(a-1,d)-f(b,c-1)+f(a-1,c-1)); } return 0; }