Min-max容斥学习笔记

min-max容斥

给定集合(S)，设(max(S))为其中最大值,(min(S))为最小值
有
(max(S)=sum_{T in S}(-1)^{|T|+1}min(T))
(min(S)=sum_{T in S}(-1)^{|T|+1}max(T))

k-th min-max容斥

(max(S,k)=sum_{T in S}(-1)^{|T|+k}(^{|T|-1}_{ k-1})min(T))

一些推导

(lcm(S)=prod p_i^{max(S)}=prod p_i^{sum_{T in S}(-1)^{|T|+1}min(T)})
(=prod_{T in S}prod p_i^{min(T)(-1)^{|T|+1}} = prod gcd(T)^{(-1)^{|T|+1}})
同理(gcd(S)=prod lcm(T)^{(-1)^{|T|+1}})

注意：这里的(T)不能为空集，因为空集没有定义