题意：对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) = k，gcd(x,y)函数为x和y的最大公约数。
ans=sigma(1)（a<=x<=b,c<=y<=d, gcd(x,y)=k）
即 ans=sigma(1) （floor(a/k)<=x<=floor(b/k), floor(c/k)<=y<=floor(d/k) , gcd(x,y)=1)
根据容斥原理转化为：
ans=sigma(1)（1<=i<=floor(b/k)，1<=j<=floor(d/k) ，gcd（i,j)=k)
-sigma(1) (1<=i<=floor(b/k) , 1<=j<=floor((c-1)/k), gcd(i,j)=k)
-sigma(1) (1<=i<=floor((a-1)/k)-1, 1<=j<=floor(d/k), gcd(i,j)=k)
+sigma(1) （1<=i<=floor((a-1)/k), 1<=j<=floor((c-1)/k) ,gcd(i,j)=k)
我们对其中任意一个sigma（1）处理，假设 sigma（1） （1<=i<=n,1<=j<=m,gcd（i,j)=1)
令f(i)表示范围内gcd（x,y)=i 的数对数， F（i）表示范围内 i能整除 gcd（x，y） 的数对数
易知 F(i) = floor(n/i)*floor(m/i)
由莫比乌斯反演得
f（i）=sigma（miu(d/i)*F(d)) (i能整除d）
=sigma（miu（d/i）* floor（n/d) * floor（m/d)) (i能整除d）
那么 sigma（1）= f（1）= sigma( miu（d）*floor（n/d) * floor( m/d)
枚举floor(n/d)*floor(m/d) 个取值，对莫比乌斯函数维护一个前缀和，计算出ans
强转int64就是快..
var t,a,b,c,d,k :longint; ans :int64; flag :array[0..50010] of boolean; prime :array[0..50010] of longint; mu :array[0..50010] of longint; function min(a,b:longint):longint; begin if a<b then exit(a) else exit(b); end; procedure pre_do; var i,j:longint; t:longint; begin t:=0; mu[1]:=1; for i:=2 to 50000 do begin if not flag[i] then begin inc(t); prime[t]:=i; mu[i]:=-1; end; for j:=1 to t do if (i*prime[j]>50000) then break else begin flag[i*prime[j]]:=true; if (i mod prime[j]<>0) then mu[i*prime[j]]:=-mu[i] else begin mu[i*prime[j]]:=0; break; end; end; end; for i:=1 to 50000 do mu[i]:=mu[i-1]+mu[i]; end; function find(n,m:longint):int64; var i:longint; ans,last:int64; begin ans:=0; i:=1; n:=n div k;m:=m div k; while (i<=n) and (i<=m) do begin last:=min(n div (n div i),m div (m div i)); ans:=ans+int64(n div i)*int64(m div i)*(mu[last]-mu[i-1]); i:=last+1; end; exit(ans); end; begin pre_do; read(t); while (t>0) do begin dec(t); read(a,b,c,d,k); ans:=find(b,d)-find(a-1,d)-find(b,c-1)+find(a-1,c-1); writeln(ans); end; end. ——by Eirlys