假定n<m

\[\sum_{isprime(p)}\sum_{a=1}^n\sum_{b=1}^mgcd(a,b)==p\]

\[\sum_{isprime(p)}\sum_{a=1}^{\left \lfloor \frac{n}{p} \right \rfloor}\sum_{b=1}^{\left \lfloor \frac{m}{p} \right \rfloor}gcd(a,b)==1\]

\[\sum_{isprime(p)}\sum_{a=1}^{\left \lfloor \frac{n}{p} \right \rfloor}\sum_{b=1}^{\left \lfloor \frac{m}{p} \right \rfloor}\sum_{d|a\&d|b}\mu(d)\]

\[\sum_{isprime(p)}\sum_{d=1}^{\left \lfloor \frac{n}{p} \right \rfloor}\mu(d) {\left \lfloor \frac{n}{pd} \right \rfloor}{\left \lfloor \frac{m}{pd} \right \rfloor}\]

但是做到这里我们发现直接枚举质数仍然会出事TAT，继续搞

\[\sum_{isprime(p)\&p|d}\sum_{d}^{n} \mu \left( \frac{d}{p} \right) {\left \lfloor \frac{n}{d} \right \rfloor}{\left \lfloor \frac{m}{d} \right \rfloor}\]

令\[f(d)=\sum_{isprime(p)\&p|d}\mu \left( \frac{d}{p} \right)\]

则原式变为

\[\sum_{d=1}^{n} {\left \lfloor \frac{n}{d} \right \rfloor}{\left \lfloor \frac{m}{d} \right \rfloor}f(d)\]

联系 \(\mu\) 函数的定义，设h为d的质因子个数，g为d质因子指数和可得

$$f(d)= \begin{cases} -\mu \left (d \right ) s& h=g\\ \left ( -1 \right )^s& h+1=g\\ 0& Otherwise \end{cases}$$