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}}\)