莫比乌斯反演
莫比乌斯函数(mu)的定义：
[begin{eqnarray}mu(i)&=&0(i含有平方因子)\&=&(-1)^{i的因子个数}(i不含有平方因子数)end{eqnarray}]
(mu)的性质：
积性函数（不完全）
重要公式：(sum_{d|n}mu(d)=(n==1))
证明：
n等于1时结论显然
否则将(mu(d))当做容斥系数来证明
例题1：
(sum_{i=1}^nsum_{j=1}^m(gcd(i,j)==1))
(n,mle10^7)
题解：
考虑原式：(sum_{i=1}^nsum_{j=1}^m(gcd(i,j)==1))
原式等于：(sum_{i=1}^nsum_{j=1}^{m}sum_{d|gcd(i,j)}mu(d))
这样在(gcd(i,j)！=1)时对答案无贡献，而在它等于1是对答案贡献唯一，符合原式
枚举(d)
如果(d)是(gcd(i,j))的因数，那么
(d|i)&&(d|j)
对于每个d来说
在1到n的范围中有(lfloor frac{n}{d}rfloor)
在1到m的范围中有(lfloor frac{m}{d}rfloor)
相应的(d)作为(gcd(i,j))的因数就该有(lfloor frac{n}{d}rfloorlfloor frac{m}{d}rfloor)多次
也意味着(mu(d))出现了那么多次
那么我们枚举$d $
既：(sum_{d=1}^{n}lfloor frac{n}{d}rfloorlfloor frac{m}{d}rfloormu(d))
这里d从1到n还是从1到m都无所谓
因为有若(d)大于(n,m)其中一个那么向下取整就会变为0，既对答案无贡献
我们发现(lfloor frac{n}{d}rfloor)和(lfloor frac{m}{d}rfloor)都最多只有(sqrt{n})和(sqrt{m})种取值，那么枚举这些取值，先预处理(mu)的前缀和，就能在根号级别的时间里解决原题了。
例题2：
(sum_{i=1}^nsum_{j=1}^m(gcd(i,j)==prime))
(n,mle10^7)
题解：
[begin{eqnarray}原式&=&sum_{i=1}^nsum_{j=1}^m(gcd(i,j)==prime)\枚举gcd&=&sum_{xin prime}sum_{i=1}^{lfloor frac{n}{x}rfloor}sum_{j=1}^{lfloorfrac{m}{x}rfloor}(gcd(i,j)==1)\借用上一题公式：&=&sum_{xin prime}sum_{d=1}^{n}lfloor frac{n}{dx}rfloorlfloor frac{m}{dx}rfloormu(d)\枚举dx &=&sum_{k=1}^{n}lfloor frac{n}{k}rfloorlfloor frac{m}{k}rfloorsum_{xin prime&x|k}mu(frac{k}{x})end{eqnarray}]
在线性筛时恰好可以处理右边的前缀和，那么就同上一题一样直接上就好了。
至于其他的题目，对于每次式子不断换着东西来枚举，枚举到符合复杂度的形式即可√
- 还没有人评论，欢迎说说您的想法！
客服
