Math

数论

素数筛

从欧拉筛的角度来看, 考虑 [1,n][1,n] 内的数, 所有大于 n\sqrt{n} 的合数一定会被某个小于等于 n\sqrt{n} 的质数(最小的质因子一定小于等于 n\sqrt{n},如果最小的质因子大于 n\sqrt{n},要么他本身是一个质数,否则 p1p2>nn=np_1p_2 > \sqrt{n}\cdot{\sqrt{n}} = n 矛盾)筛掉. 所以当 nn 很大时,可以只筛出 n\sqrt{n} 内的质数,用这些质数去(分段)筛大于 n\sqrt{n} 的那些数.

关于 gcd 容斥

如果遇到这样一类求和

T=AS(a1,a2,,an,k1,k2,,km)f(A)T = \sum_{A \subseteq S}{(a_1, a_2, \dots, a_n, k_1, k_2, \dots, k_m) \cdot f(A)}

其中 aia_i 是集合 AA 里的元素,kjk_j 是额外需要求gcd的元素. 记 K=k1k2kmK = k_1k_2\cdots{}k_m.

可以枚举 gcd,转换为

T=dK(dAS[d=(a1,a2,,an,k1,k2,,km)]f(A))T = \sum_{d|K}{\left(d \cdot \sum_{A \subseteq S}{[d = (a_1,a_2,\dots,a_n, k_1, k_2, \dots, k_m)]\cdot{}f(A)}\right)}

一般 f(A)f(A) 仅与集合 AA 的大小有关,即

f(A)=h(A)f(A) = h(|A|)

则有

T=dK(dl=1Sh(l)ASA=l[d=(a1,a2,,an,k1,k2,,km)])T = \sum_{d | K}{\left(d \cdot \sum_{l = 1}^{|S|}{h(l)\sum_{A\subseteq{S}\:\text{且}\:|A|=l}{[d = (a_1,a_2,\dots,a_n,k_1,k_2,\dots,k_m)]}}\right)}

遍历集合 SS 的每个数的因子,统计出因子 dd 的出现次数为 cdc_d, 那么大小为 llgcd 至少为 dd 的集合的个数为

g(d,l)=(cdl)g(d,l) = \binom{c_d}{l}

ϕ(d)=l=1min{cd,S}h(l)g(d,l)\phi(d) = \sum_{l = 1}^{\min\{c_d,|S|\}}{h(l)g(d,l)}

gcddd 的集合的贡献为

Φ(d)=ϕ(d)t(K/d)Φ(t)\Phi(d) = \phi(d) - \sum_{t | (K / d)}\Phi(t)

容斥一波就可以搞出来了

T=dKdΦ(d)T = \sum_{d | K}{d \cdot \Phi(d)}

一些常见的 h(l)h(l),一般 cdSc_d \le |S|:

  • h(l)=lh(l) = l, ϕ(d)=l=1cdl(cdl)=cd2cd11\phi(d) = \sum_{l=1}^{c_d}{l\binom{c_d}{l}} = c_d \cdot 2^{c_d-1} - 1
  • h(l)=λlh(l) = \lambda^{l}, ϕ(d)=l=1cdλl(cdl)=(1+λ)cd1\phi(d) = \sum_{l=1}^{c_d}{\lambda^l\binom{c_d}{l}} = (1 + \lambda)^{c_d} - 1
Last Updated: 8/19/2018, 11:05:05 AM