Link:https://www.lydsy.com/JudgeOnline/problem.php?id=2301
Algorithm:
分析：令g(n,m)表示在1<=x<=n,1<=y<=m，满足gcd(x,y)是k的(x,y)的对数。
那么由容斥原理可得
满足gcd(x,y)是k的(x,y)的对数也等价于1<=x<=n/k,1<=y<=m/k,(x,y)互质的对数，即
令f(i)表示满足gcd(x,y)=i时(x,y)的对数
F(i)表示满足i|gcd(x,y)的(x,y)的对数，则F(i)=?ni??mi?。
发现[n/d] 最多有2sqrt(n) 个取值，那么 (n/d)*(m/d)就至多有2sqrt(n)+2sqrt(m)个取值（并不是*，对于每个d n/(sqrt(n)+1)<d<=n ， (n/d)*(m/d)仍只有一个值）
于是我们发现会有连续的一段(n/d)*(m/d)的值相同，便可以使用分块来优化（细节待填坑）
Code:
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN=5e4+10; inline ll read() { char ch;ll num,f=0; while(!isdigit(ch=getchar())) f|=(ch==‘-‘); num=ch-‘0‘; while(isdigit(ch=getchar())) num=num*10+ch-‘0‘; return f?-num:num; } int a,b,c,d,k; int sum[MAXN],mo[MAXN],pri[MAXN],cnt; bool mark[MAXN]; void getmo() { mo[1]=1; for(int i=2;i<=5e4;i++) { if(!mark[i]){mo[i]=-1;pri[++cnt]=i;} for(int j=1;j<=cnt && i*pri[j]<=5e4;j++) { mark[i*pri[j]]=1; if(i%pri[j]==0){mo[i*pri[j]]=0;break;} else mo[i*pri[j]]=-mo[i]; } } for(int i=1;i<=5e4;i++) sum[i]=sum[i-1]+mo[i]; } int cal(int n,int m) { n/=k;m/=k; if(n>m)swap(n,m); int ret=0,pos; for(int i=1;i<=n;i=pos+1) { pos=min(n/(n/i),m/(m/i)); ret+=(sum[pos]-sum[i-1])*(n/i)*(m/i); } return ret; } int main() { getmo(); int T=read(); while(T--) { a=read();b=read();c=read();d=read();k=read(); int res=cal(a-1,c-1)+cal(b,d)-cal(a-1,d)-cal(b,c-1); printf("%d\n",res); } return 0; }
Review:
1、GCD（x,y）=k --------> x/k,y/k互质
方便使用欧拉函数或莫比乌斯反演解题
2、使用分块对莫比乌斯反演的优化（待填）
原文：https://www.cnblogs.com/newera/p/9077511.html