莫比乌斯反演
基础公式
[F(n)=sum_{d|n}f(d)\f(n)=sum_{d|n}F(d)μ(frac{n}{d})
]
一般使用的公式
[[gcd(i,j)=1]=sum_{d|gcd(i,j)}mu(d)\sum_{d|n}mu(d)=[n=1]\---------------------
]
[sum_{i=1}^nsum_{j=1}^m[gcd(i,j)=x]=sum_{d=1}^{min({lfloorfrac{n}{x}
floor},{lfloorfrac{m}{x}
floor})}{lfloorfrac{n}{dx}
floor}{lfloorfrac{m}{dx}
floor}
]
例子
1.
[sum_{i=1}^{n}sum_{j=1}^{m}[gcd(i,j)=k] (n<m)\Downarrow \=sum_{i=1}^{lfloorfrac{n}{k}
floor}sum_{j=1}^{lfloorfrac{m}{k}
floor}[gcd(i,j)=1]
]
2.
[sum_{i=1}^{n}sum_{j=1}^{m}[gcd(i,j)=1] (n<m)\Downarrow\=sum_{i=1}^{n}sum_{j=1}^{m}sum_{d|gcd(i,j)}mu(d)
]