(1) 常用公式;
由莫比乌斯函数的容斥意义易得.
\(\sum_{} F(...)[gcd(...)==1]\)
\(=\sum_{i} F(i)\sum_{d|i} μ(d)\)
\(=\sum_{d}μ(d)\sum_{k} F(kd)\)
枚举 \(gcd\) 可知,
- \(\sum_{
- i=1
- }^N \sum_{
- j=1
- }^M F(gcd(i,j))\)
- \(=\sum_{
- i=1
- }^N \frac{
- N
- }{
- i
- } \frac{
- M
- }{
- i
- } \sum_{
- d|i
- } μ(d)F(i/d)\)
来源: http://www.bubuko.com/infodetail-2946249.html