officeyutong

众所周知，这题不是个人也会。

$$ \text{首先可知}d\left( nm \right) =\sum_{a|n}{\sum_{b|m}{\left[ 阅读全文..

众所周知，这题是个人就会。

$$ \text{钦定}N\le M \\ \sum_{1\le i\le N}{\sum_{1\le j\le M}{\left[ \mathrm{gcd}\left( i,j \right) =p \right]}} \\ \sum_p{\sum_{1\le pi\le N}{\sum_{1\le pj\le M}{\left[ \mathrm{gcd}\left( pi,pj \right) =p \right]}}} \\ \sum_p{\sum_{1\le i\le \lfloor \frac{N}{p} \rfloor}{\sum_{1\le j\le \lfloor \frac{M}{p} \rfloor}{\left[ \mathrm{gcd}\left( i,j \right) =1 \right]}}} \\ \sum_p{\sum_{1\le i\le \lfloor \frac{N}{p} \rfloor}{\sum_{1\le j\le \lfloor \frac{M}{p} \rfloor}{\sum_{k|gcd\left( i,j \right)}{\mu \left( k \right)}}}} \\ \sum_p{\sum_{1\le k\le \lfloor \frac{N}{p} \rfloor}{\sum_{1\le ik\le \lfloor \frac{N}{p} \rfloor}{\sum_{1\le jk\le \lfloor \frac{M}{p} \rfloor}{\sum_{k|gcd\left( ik,jk \right)}{\mu \left( k \right)}}}}} \\ \sum_p{\sum_{1\le k\le \lfloor \frac{N}{p} \rfloor}{\sum_{1\le i\le \lfloor \frac{N}{kp} \rfloor}{\sum_{1\le j\le \lfloor \frac{M}{kp} \rfloor}{\mu \left( k \right)}}}} \\ \sum_{1\le p\le N,p\,\,is\,\,prime}{\sum_{1\le k\le \lfloor \frac{N}{p} \rfloor}{\mu \left( k \right) \lfloor \frac{N}{kp} \rfloor \lfloor \frac{M}{kp} \rfloor}} \\ T=kp \\ T\le N \\ \sum_{1\le T\le N}{\sum_{p|T\left( T\text{的所有质因数} \right)}{\lfloor \frac{N}{T} \rfloor \lfloor \frac{M}{T} \rfloor \mu \left( \frac{T}{p} \right)}} \\ =\sum_{1\le T\le N}{\lfloor \frac{N}{T} \rfloor \lfloor \frac{M}{T} \rfloor \sum_{p|T,\left( T\text{的所有质因数} \right)}{\mu \left( \frac{T}{p} \right)}} $$