首先需要知道 \(f\) 是个啥
这里直接给出结论，过程可以看大佬的博客
\(f(n) = 2f(n - 1) + f(n - 2)\)
\(f(0)=0\)
\(f(1)=1\)
这种类似 斐波那契数列的递推式有结论 \(gcd(f(x), f(y)) = f(gcd(x, y))\) 通过辗转相减证明
那么一个集合的 \(gcd\) 是好求的，所以考虑进行 \(min-max\) 容斥
有
\(lcm(S)=\prod_{T \subset S,T \ne \not\empty}gcd(T)^{(-1)^{|T| - 1}}\)
那我们求的就是
\[ \prod_{T \subset S,T \ne \not\empty}f(gcd(T))^{(-1)^{|T| - 1}} \]\[ = \prod_{d= 1}^{n}f(d)^{\sum_{T \subset S,T \ne \not\empty}[gcd(T) = d](-1)^{|T| - 1}} \]现在只处理角标
\[ \sum_{T \subset S,T \ne \not\empty}[gcd(T) = d](-1)^{|T| - 1} \]\[= \sum_{T \subset S,T \ne \not\empty}\sum_{x|\frac{gcd(T)}{d}}\mu(x)(-1)^{|T| - 1} \]\[= \sum_{T \subset S,T \ne \not\empty}\sum_{xd | gcd(T)}\mu(x)(-1)^{|T| - 1} \]\[= \sum_{x= 1}^{\frac{n}{d}}\mu(x)\sum_{T \subset S`}(-1)^{|T| - 1} \]其中 \(s`\) 为 \(s\) 中 \(xd\) 的倍数除以 \(xd\)，即\({1, 2, .. \frac{n}{xd}}\)
\[\sum_{T \subset S`,T \ne \not\empty}(-1)^{|T| - 1} \]\[=\sum_{i = 1}^{size}(-1)^{i + 1} \]\[=-\sum_{i = 1}^{size}(-1)^i \]\[ = 1- \sum_{i = 0}^{size}(-1)^i \]\[ =1-[T = \empty] \]那么带回去
\[\sum_{x= 1}^{\frac{n}{d}}\mu(x)\sum_{T \subset S`}(-1)^{|T| - 1} \]因为 \(dx <= n\) 所以\(S`\)非空
\[ =\sum_{x= 1}^{\frac{n}{d}}\mu(x) \]于是我们要求的变成
\[ = \prod_{d= 1}^{n}f(d)^{\sum_{x= 1}^{\frac{n}{d}}\mu(x)} \]考虑 \(dx <= n\) 的都会产生贡献，我们枚举 \(i = dx\)，式子就是
\[= \prod_{i= 1}^{n}\prod_{d|i}f(\frac{i}{d})^{\mu(d)} \] 标签：subset,frac,gcd,题解,sum,公倍,佩尔,ne,empty From： https://www.cnblogs.com/Chencgy/p/17090829.html