Loj6102. 「2017 山东二轮集训 Day1」第三题（min-max 反演）
题目大意
输入一个大小为 (n) 的集合 (S)，求 (lcm_{k∈S}f_k)，其中 (f_k) 是第 (k) 个 Fibonacci 数。
数据范围
$ n le 5 cdot 10^4,k le 10^6$
解题思路
有人说是经典题，我觉得是神仙题
首先要有一些前置知识
- 莫比乌斯反演
- min-max 容斥
- (gcd(f_i, f_j) = f_{gcd(i, j)})
首先一步 min-max 反演
[large lcm(f_S)=prod_{varnothing
e Tsubseteq S}gcd(f_k)_{k in T}^{(-1)^{|T|-1}}
]
解释一下，将每个质因子分开考虑，它们可以分别 min-max 容斥，原来 min-max 的加法通过变成指数变成了乘法，各个质因子是独立的，因此可以一起计算
[large lcm(f_S)=prod_{varnothing
e Tsubseteq S}f_{gcd(k)_{k in T}}^{(-1)^{|T|-1}}
]
这一步用了 (gcd(f_i, f_j) = f_{gcd(i, j)})
然后看到 gcd 就会想到反演（真能想到吗），设 (f_i = prod_{d|i} g_d)，有 (g_i = f_iprod_{d|i and d eq i} g_d^{-1})
[large lcm(f_S)=prod_{varnothing
e Tsubseteq S}{(prod_{d|gcd(k)}g_d})^{(-1)^{|T|-1}}\
large lcm(f_S) = prod_d g_d^{sum_{varnothing
e Tsubseteq S_d}(-1)^{|T|-1}}
]
其中 (S_d = {x | x in S and d| x}) ，容易（真的容易吗）发现 (sum_{T subseteq S} (-1)^{|T|-1} = 0)
所以 (sum_{varnothing eq T subseteq S} (-1)^{|T|-1} = 1(|S| eq varnothing))
因此有
[large lcm(f_S)= prod_{exists k, d | k} g_d
]
代码就很简单了吧