题意
给出 \(n\) 个正整数 \(a_1,a_2\cdots,a_n\)，求 \(\operatorname{lcm}(F_{a_1}, F_{a_2},\cdots, F_{a_n})\)。
其中 \(\{F_i\}\) 为斐波那契数列。
\(2\le n\le 50000, 1\le a_i\le 1000000\)
3s
解答
斐波那契数列的最小公倍数很难直接求，但是其最大公约数却有优美的结论 \(\gcd(F_n, F_m) = F_{\gcd(n, m)}\)，于是考虑将最小公倍数转化成最大公约数。
此处有 \(\mathrm{Min-Max}\) 反演的经典推论：
\[\operatorname{lcm}(S) = \prod_{T\subseteq S\land T\not=\varnothing} \left(\gcd(T)\right)^{(-1)^{|T|-1}} \]证明很简单，分别考虑每个质因子，\(\operatorname{lcm}\) 就是求其 \(\max\)，\(\gcd\) 就是求其 \(\min\)，即证。
接下来开始推柿子：
\[\begin{split} \operatorname{lcm}(F_s(s\in S)) &=\prod_{T\subseteq S\land T\not ={\varnothing}}\gcd(F_t(t\in T))^{(-1)^{|T|-1}} \\ &=\prod_{T\subseteq S\land T\not ={\varnothing}}F_{\gcd(T)}^{(-1)^{|T|-1}} \end{split} \]第一步转化完毕！
接下来肯定不能直接枚举子集算，于是进行下一步的推倒：
我们用 \(c_i\) 表示 \(i\) 的倍数出现的次数。
对每个 \(x\) 分别考虑 \(F_x\) 的次数：
\[\begin{split} \sum_{x | T} [\gcd(T) = x](-1)^{|T|-1} &=\sum_{x | T} [\gcd\left(\frac T x\right) = 1](-1)^{|T|-1} \\ &= \sum_{x | T} \sum_{d|\frac Tx } \mu(d)(-1)^{|T|-1} \\ &= \sum_{d=1}^\infty \mu(d)\sum_{i = 1}^{c_{d\cdot x}}\binom{c_{d\cdot x}}{i}(-1)^{-1} \\ &= \sum_{d=1}^\infty \mu(d) [c_{d\cdot x} > 0] \end{split} \]其中第三行中的 \(i\) 为枚举 \(|T|\)。
于是对于每个 \(x\) 枚举 \(d\) 计算，总复杂度是调和级数级别的，也就是 \(\mathcal{O}(n\log n)\) 的。
于是总复杂度为 \(\mathcal{O}(n\sqrt n)\)，瓶颈在于枚举因子。
标签：le,gcd,51nod,sum,1355,split,lcm,operatorname From： https://www.cnblogs.com/0922-Blog/p/51nod_1355.html