题目传送门 这个问题等价于询问有多少个数对(x,y)满足l<=x<=floor(n/k),1<=y<=floor(m/k)且x与y互质 首先我们根据容斥原理将一个询问拆分为四个询问即ans=f(b,d)-f(a-1,d)-f(b,c-1)+f(a-1,c-1) f(i)为gcd(x,y)=i的个数(1<=x<=n,1<=y<=m) 我们令F(i)为i|gcd(x,y)的个数(1<=x<=n,1<=y<=m) 则可以得到
F(i)=∑i|df(i)
f(i)=∑i|dμ(di)F(d)
又因为
F(i)=⌊ni⌋⌊mi⌋
f(i)=∑i|dμ(di)⌊nd⌋⌊md⌋
这样做是O(n)的，但因为是多组询问所以依旧会T掉。
所以我们需要一个有效的时间优化。 通过观察我们可以发现， ⌊nd⌋ 中最多只有 2n−√ 个取值，同理可得 ⌊md⌋ 中也最多只会有 2m−−√ 个取值。那么最终的答案个数是最多为 2(n−√+m−−√) 个。我们只需枚举这 2(n−√+m−−√) 个取值，即可以以O( n−√ )的时间复杂度求解。同时如果要实现这样做，代码是十分简单。所以可以画一个表格来加深理解，方便写代码。
⌊nd⌋ ⌊md⌋ ans11…12…22…22…23…通过上表，可知第三四行的前两列完全一样，所以我们可以求出莫比乌斯函数的前缀和，然后通过一步算出。
for(int i=1;i<=x;i=last+1) { last=min(x/(x/i),y/(y/i)); ans+=(x/i)*(y/i)*(sum[last]-sum[i-1]); }sum数组就是我们所求的前缀和，last相当于是找一个符合条件的位置。 完整代码如下：
#include<cstdio> #include<cstring> #include<algorithm> #define MAXN 50000 using namespace std; int a,b,c,d,k; int miu[MAXN+5],prime[MAXN+5],sum[MAXN+5]; void Init() { miu[1]=1; int cnt=0; bool check[MAXN+5]; memset(check,0,sizeof check); for(int i=2;i<=MAXN;i++) { if(!check[i]) { prime[++cnt]=i; miu[i]=-1; } for(int j=1;j<=cnt;j++) { if(prime[j]*i>MAXN) break; check[prime[j]*i]=1; if(i%prime[j]==0) { miu[i*prime[j]]=0; break; } miu[i*prime[j]]=-miu[i]; } } for(int i=1;i<=MAXN;i++) sum[i]=sum[i-1]+miu[i]; } int num(int x,int y) { x/=k; y/=k; int ans=0,last; if(x>y) swap(x,y); for(int i=1;i<=x;i=last+1) { last=min(x/(x/i),y/(y/i)); ans+=(x/i)*(y/i)*(sum[last]-sum[i-1]); } return ans; } int main() { Init(); int T; scanf("%d",&T); while(T--) { scanf("%d%d%d%d%d",&a,&b,&c,&d,&k); printf("%d\n",num(b,d)-num(a-1,d)-num(b,c-1)+num(a-1,c-1)); } }