---

---

\(solution:\)

这道题完全跟 用的一个套路。

我们可以列出答案就是要我们求：

\(ans=\sum_{p\in prime}\sum_{i=1}^{n}{\sum_{j=1}^{m}{[gcd(i,j)==p]}}\)

我们发现后面那一部分（\(\sum_{i=1}^{n}{\sum_{j=1}^{m}{[gcd(i,j)==p]}}\)）可以套路的莫比乌斯反演：

\(ans=\sum_{p\in prime}\sum_{i=1}^{\frac{n}{p}}{\sum_{j=1}^{\frac{m}{p}}{[gcd(i,j)==1]}}\)

\(ans=\sum_{p\in prime}\sum_{i=1}^{\frac{n}{p}}{\sum_{j=1}^{\frac{m}{p}}{\sum_{k|gcd(i,j)}{\mu(k)}}}\)

\(ans=\sum_{p\in prime}\sum_{k}^{min(n,m)}{\mu(k)}{\sum_{i=1}^{\frac{n}{p}}{\sum_{j=1}^{\frac{m}{p}}{[k|gcd(i,j)]}}}\)

\(ans=\sum_{p\in prime}\sum_{k}^{min(n,m)}{\mu(k)\times \lfloor \frac{n}{p\times k} \rfloor \times \lfloor \frac{m}{p\times k} \rfloor}\)

我们发现后面那两个东西有点麻烦，我们想办法让它变成常数项：

设： \(T=p\times k\)

\(ans=\sum_{t=1}^{min(n,m)} \lfloor \frac{n}{T} \rfloor \times \lfloor \frac{m}{T} \rfloor \sum_{p|T，p\in prime} \mu{\frac{T}{p}}\)

然后我们发现后面那一部分（\(\sum_{p|T，p\in prime} \mu{\frac{T}{p}}\)）可以预处理，然后我们在前面用整除分块，这样就可以每次只用\(log(min(n,m))\)的时间完成单个询问了！

---

---

\(code:\)

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include