数学公式测试TAT
假定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}$$