题目大意：

　　$q(q\leq50000)$组询问，对于给定的$a,b,c,d(a,b,c,d\leq50000)$，求$\displaystyle\sum_{i=a}^b\sum_{j=c}^d[\gcd(i,j)=k]$。

思路：

　　首先可以利用容斥原理，将$(a,b,c,d)$的询问拆成$(b,d)$、$(a-1,d)$、$(b,c-1)$和$(a-1,c-1)$四个询问，对于询问$(n,m)$，有：

$$

\begin{align*}

&\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=k]\\

&=\sum_{k=1}^{\min(n,m)}\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}[\gcd(i,j)=1]\\

&=\sum_{k=1}^{\min(n,m)}\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{k}\rfloor}\sum_{d|\gcd(i,j)}\mu(d)\\

&=\sum_{k=1}^{\min(n,m)}\sum_{d=1}^{\min(\lfloor\frac{n}{k}\rfloor,\lfloor\frac{m}{k}\rfloor)}\mu(d)\sum_{1\leq i\leq\lfloor\frac{n}{k}\rfloor且d|i}\sum_{1\leq i\leq\lfloor\frac{m}{k}\rfloor且d|j}1\\

&=\sum_{k=1}^{\min(n,m)}\sum_{d=1}^{\min(\lfloor\frac{n}{k}\rfloor,\lfloor\frac{m}{k}\rfloor)}\mu(d)\lfloor\frac{\lfloor\frac{n}{k}\rfloor}{d}\rfloor\lfloor\frac{\lfloor\frac{m}{k}\rfloor}{d}\rfloor

\end{align*}

$$

　　$\mu$的前缀和可以预处理。因此到最后一步时，复杂度已经是$O(n)$的了，然而$q\leq50000$，还是会TLE。考虑某些时候对于某一范围内的$k$，$\lfloor\frac{\lfloor\frac{n}{k}\rfloor}{d}\rfloor$和$\lfloor\frac{\lfloor\frac{m}{k}\rfloor}{d}\rfloor$分别各自相等，因此我们可以将相等的情况一起考虑，这样总共有$O(\sqrt n)$种情况，时间复杂度$O(q\sqrt n)$。

1 #include
     
       2 #include
      
        3 #include
       
         4 typedef long long int64; 5 inline int getint() { 6     register char ch; 7     while(!isdigit(ch=getchar())); 8     register int x=ch^'0'; 9     while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');10     return x;11 }12 const int N=50001,M=5134;13 bool vis[N];14 int mu[N],sum[N],p[M];15 inline void sieve() {16     mu[1]=1;17     for(register int i=2;i