首先对于询问 $x,a,b$ 答案就是 $f[x]=sum_{i=1}^{a}sum_{j=1}^{b}[gcd(i,j)==x]$
看到 $gcd(i,j)$，莫比乌斯反演走起
设 $F[x]=sum_{i=1}^{a}sum_{j=1}^{b}[x|gcd(i,j)]$
那么有 $F[x]=sum_{x|d}f[d]$ 且考虑 $F[x]$ 的意义发现 $F[x]=left lfloor frac{a}{x} ight floor left lfloor frac{b}{x} ight floor$
直接反演：$f[x]=sum_{x|d}mu (d/x)F[d]=sum_{x|d}mu (d/x)left lfloor frac{a}{d} ight floor left lfloor frac{b}{d} ight floor$
考虑枚举 $x$ 的倍数 $k$，那么：$f[x]=sum_{k}mu(k)left lfloor frac{a}{kx} ight floorleft lfloor frac{b}{kx} ight floor$
因为 $left lfloor frac{a}{kx} ight floor=left lfloor frac{left lfloor frac{a}{x} ight floor}{k} ight floor$
所以 $f[x]==sum_{k}mu(k)left lfloor frac{left lfloor frac{a}{x} ight floor}{k} ight floorleft lfloor frac{left lfloor frac{b}{x} ight floor}{k} ight floor$
然后直接数论分块就好了，单次询问复杂度 $O( sqrt (n) )$
总复杂度 $O(n sqrt (n) )$
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=2e6+7,M=5e4; int Q,n,m,d,pri[N],mu[N],sum[N],tot; ll f[N],F[N],ans; bool not_pri[N]; void pre() { not_pri[1]=1; mu[1]=1; for(int i=2;i<=M;i++) { if(!not_pri[i]) pri[++tot]=i,mu[i]=-1; for(int j=1;j<=tot;j++) { ll t=1ll*i*pri[j]; if(t>M) break; not_pri[t]=1; if(!(i%pri[j])) break; mu[t]=-mu[i]; } } for(int i=1;i<=M;i++) sum[i]=sum[i-1]+mu[i]; } int main() { Q=read(); pre(); while(Q--) { n=read(),m=read(),d=read(); n/=d; m/=d; int mx=min(n,m); ans=0; for(int l=1,r=0;l<=mx;l=r+1) { r=min(mx, min(n/(n/l),m/(m/l)) ); ans+=1ll*(sum[r]-sum[l-1])*(n/l)*(m/l); } printf("%lld ",ans); } return 0; }