整除分块
这个是学习莫比乌斯反演需要的预备知识,几乎所有这类的题都需要用到这个。
考虑下面这个式子:
[sum_{i=1}^{n}lfloorfrac{n}{i}
floor
]
这个当然可以(O(n))算,但是很多时候这样还不够快,于是下面有一个(O(sqrt{n}))的算法。
通过打表可以发现,当(i)为连续一段时,后面那玩意都是一样的。
然后对于(i),最后一个和它相同的位置是(n/(n/i)),注意这里都是整除,然后共有(O(sqrt{n}))个块,所以我们就可以每次跳一个块,快速算出结果,代码如下:
int n;read(n);
int ans=0,T=1;
while(T<=n) {
int pre=T;T=n/(n/T);
ans=ans+(T-pre+1)*(n/T);T++;
}
write(ans);
莫比乌斯函数
关于莫比乌斯函数,其实并不是一个很玄学的东西,它本质上就是一个容斥系数。
对于莫比乌斯函数,它写作(mu(d)),定义如下:
- (mu(1)=1)。
- 对于(d)进行分解,(d=prod_{i=1}^ka_i^{p_i}),若(forall i,p_i=1),则(mu(d)=(-1)^k)。
- 否则(mu(d)=0)。
然后对于这个函数有一个最为重要的性质:
[sum_{d|n}mu(d)=[n=1]
]
证明其实很简单,将(n)进行唯一分解,得到(n=prod_{i=1}^ka_i^{p_i})只需要考虑容斥,对于(n)的每一个因数只能选或不选,则:
[sum_{d|n}mu(d)=sum_{i=0}^{k}(-1)^iinom{k}{i}=[k=0]
]
然后([k=0])其实等价于([n=1]),得证。
线筛也很简单,根据定义就可以了,代码:
void sieve() {
mu[1]=1;
for(int i=2;i<maxn;i++) {
if(!vis[i]) pri[++tot]=i,mu[i]=-1;
for(int t,j=1;j<=tot&&i*pri[j]<maxn;j++) {
vis[t=i*pri[j]]=1;
if(!(i%pri[j])) {mu[t]=0;break;}
mu[t]=-mu[i];
}
}
}
莫比乌斯反演
前置知识讲完了,其实真的很水。
定义(f(n))和(g(n)),已知:
[f(n)=sum_{d|n}g(d)
]
然后已知(f),求(g)。
其实这个和推容斥差不太多,由于我想把前面的莫比乌斯函数的性质用上,所以先说一句废话:
[g(n)=sum_{d|n}[frac{n}{d}=1]g(d)
]
然后发现这个东西和上面长的很像,带进去:
[egin{align}
g(n)&=sum_{d|n}sum_{i|frac{n}{d}}mu(i)g(d)\
&=sum_{d|n}g(d)sum_{i|frac{n}{d}}mu(i)
end{align}
]
然后先枚举(i):
[egin{align}
g(n)&=sum_{i|n}mu(i)sum_{d|frac{n}{i}}g(d)
end{align}
]
然后后面那个式子其实就是(f),所以:
[g(n)=sum_{d|n}mu(d)f(frac{n}{d})
]
然后就做完了。
这个东西就是莫比乌斯反演:
已知
[f(n)=sum_{d|n}g(d)
]
那么可以得到:
[g(n)=sum_{d|n}mu(d)f(frac{n}{d})
]
其实做题的话,直接把(sum_{d|n}mu(d)=[n=1])带到题目给的式子里更好推一些。
最主要的还是多做题,做多了就会发现其实都是一个套路,还有就是式子要自己拿纸笔来推,这点很重要。
习题
(题目难度基本按顺序排列,推荐按顺序写)