莫比乌斯函数。

不妨设N>=M。

我们发现，坐标(x,y)到(0,0)的连线上有gcd(x,y)个点（包含自己）。

所以答案就是：

$$\sum_{1\leq x\leq N,1\leq y\leq M}2[gcd(x,y)-1]+1$$

$$=\sum_{1\leq x\leq N,1\leq y\leq M}2gcd(x,y)-1$$

$$=2\sum_{1\leq x\leq N,1\leq y\leq M}gcd(x,y)-N*M$$

$其实就是求：$

$$\sum_{1\leq x\leq N,1\leq y\leq M}gcd(x,y)$$

$设g=gcd(x,y)，则x=gx',y=gy',gcd(x',y')=1，原式变成：$

$$\sum_{1\leq g\leq M}g\sum_{1\leq x'\leq \left \lfloor\frac{N}{g}\right \rfloor,1\leq y'\leq \left \lfloor\frac{M}{g}\right \rfloor}[(x',y')==1]$$

$有一个结论：$

$$\sum_{d|n}\mu (d)=[n==1]$$

$所以：$

$$\sum_{1\leq g\leq M}g\sum_{1\leq x'\leq \left \lfloor\frac{N}{g}\right \rfloor,1\leq y'\leq \left \lfloor\frac{M}{g}\right \rfloor}\sum_{d|(x',y')}\mu(d)$$

$$\sum_{1\leq g\leq M}g\sum_{1\leq x'\leq \left \lfloor\frac{N}{g}\right \rfloor,1\leq y'\leq \left \lfloor\frac{M}{g}\right \rfloor}\sum_{d|x',d|y'}\mu(d)$$

$设x'=dx'',y'=dy''，原式变成：$

$$\sum_{1\leq g\leq M}\sum_{1\leq d\leq \left \lfloor\frac{M}{g}\right \rfloor}g\mu (d)\sum_{1\leq x''\leq \left \lfloor \frac{N}{gd} \right \rfloor}\sum_{1\leq y''\leq \left \lfloor \frac{M}{gd} \right \rfloor}1$$

$$\sum_{1\leq g\leq M}\sum_{1\leq d\leq \left \lfloor\frac{M}{g}\right \rfloor}g\mu (d)\left\lfloor \frac{N}{gd}\right \rfloor \left\lfloor \frac{M}{gd}\right \rfloor$$

$我们枚举g，其实对于1\leq d\leq \left\lfloor \frac{M}{g}\right \rfloor，\left\lfloor \frac{N}{gd}\right \rfloor的取值最多只有\sqrt{\left\lfloor \frac{N}{g}\right \rfloor}个，\left\lfloor \frac{M}{gd}\right \rfloor的取值最多只有\sqrt{\left\lfloor \frac{M}{g}\right \rfloor}个。$

$我们可以不直接枚举d，而同时从小到大枚举\left\lfloor \frac{N}{gd}\right \rfloor和\left\lfloor \frac{M}{gd}\right \rfloor的取值，然后记住\mu (d)的前缀和，累加即可。$

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