首先对于询问 $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} \right \rfloor \left \lfloor \frac{b}{x} \right \rfloor$
直接反演：$f[x]=\sum_{x|d}\mu (d/x)F[d]=\sum_{x|d}\mu (d/x)\left \lfloor \frac{a}{d} \right \rfloor \left \lfloor \frac{b}{d} \right \rfloor$
考虑枚举 $x$ 的倍数 $k$，那么：$f[x]=\sum_{k}\mu(k)\left \lfloor \frac{a}{kx} \right \rfloor\left \lfloor \frac{b}{kx} \right \rfloor$
因为 $\left \lfloor \frac{a}{kx} \right \rfloor=\left \lfloor \frac{\left \lfloor \frac{a}{x} \right \rfloor}{k} \right \rfloor$
所以 $f[x]==\sum_{k}\mu(k)\left \lfloor \frac{\left \lfloor \frac{a}{x} \right \rfloor}{k} \right \rfloor\left \lfloor \frac{\left \lfloor \frac{b}{x} \right \rfloor}{k} \right \rfloor$
然后直接数论分块就好了，单次询问复杂度 $O( \sqrt (n) )$
总复杂度 $O(n \sqrt (n) )$
#include#include #include #include #include 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\n",ans); } return 0;}
