题目传送门

题解:

首先此题可以化成四个式子容斥的形式,基础式子便是
\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[gcd(i, j)=\;\;d]
推导过程如下 :
默认n<m

\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[gcd(i, j)=\;\;d]

\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}[gcd(i, j)=\;\;1]

\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}\sum\limits_{p\mid (i, j)}\mu(p)

\sum\limits_{p=1}^{\lfloor\frac{n}{d}\rfloor}\mu(p)\lfloor\frac{n}{dp}\rfloor\lfloor\frac{m}{dp}\rfloor

然后就可以预处理莫比乌斯函数的前缀和,再对后面的\sqrt{N}求和了

代码:

#include <cstdio>#include <iostream>#include <algorithm>#include <cstring>const int N = 51000;bool np[N];int pr[N], tot, mu[N], sum[N];using namespace std;void init() { mu[1]=1; sum[1]=1; for(int i=2;i<N;i++) { if(!np[i]) { pr[++tot]=i; mu[i] = -1; } for(int j=1;j<=tot&&i*pr[j]<N;j++) { np[i*pr[j]]=1; if(i % pr[j] == 0) { mu[i*pr[j]] = 0; break; } mu[i*pr[j]]=-mu[i]; } sum[i] = sum[i-1] + mu[i]; }}long long work(int a,int b,int d) { a/=d; b/=d; if(a>b)swap(a,b); int lst = 0; long long ans=0; for(int p=1;p<=a;p=lst+1) { lst=min(a/(a/p),b/(b/p)); ans+=(long long)(sum[lst]-sum[p-1])*(a/p)*(b/p); } return ans;}int main() { int t,a,b,c, d, k; init(); //for(int i=1;i<=50000;i++) printf("%d\n",sum[i]); scanf("%d",&t); while(t--) { scanf("%d%d%d%d%d",&a,&b,&c, &d, &k); a--, c--; long long ans1 = work(b,d,k); ans1-= work(a, d, k); ans1-= work(b, c, k); ans1+= work(a, c, k); printf("%lld\n", ans1); }}