快乐猜结论
# 题面
> Linked 51nod-1355
点击展开/折叠 题面
数列 $f_n$ 表示 $f_0=0,f_1=1$,$f_n=f_{n-1}+f_{n-2}$($n\ge 2$)。
给定 $n$ 以及 $a_1,a_2,\dots,a_n$,($1\le n\le50000,1\le a_i\le10^6$)求:
$$\text{lcm}(f_{a_1},f_{a_2},\dots,f_{a_n})\bmod 10^9+7$$
# 解析
莫名其妙猜了一下 min-max反演,然后式子都没推完就把结论给猜出来了 (。^▽^)
首先有一个一般性的结论,与斐波那契无关。
假如要求 $\text{lcm}(a_1,a_2,\dots,a_n)$,先把每个数质因数分解 $a_k=\prod p_i^{b_{i,k}}$,然后 lcm 就是求
定义全集 $\mathbb U=\{1,2,\dots,n\}$,于是对指数来 min-max 反演:
根据指数的相关运算可以把指数中的 $\Sigma$ 提出来。
这就是对若干数求 lcm 的min-max反演方法。
不严谨地书写,$\gcd(\mathbb S)$ 表示 $\mathbb S$ 中所有数的 gcd;$x\mid\mathbb S$ 表示 $x$ 整除 $\mathbb S$ 中的所有数
那么运用到这道题就是,令全集 $\mathbb V=\{a_1,a_2,\dots,a_n\}$,又运用到斐波那契数列的广为人知的结论,则答案为
既然有 gcd,就可以莫比乌斯反演了 ╰( ̄ω ̄o)
令 $h(t)=\sum\limits_{\mathbb S\in\mathbb V,t\mid\mathbb S}(-1)^{|\mathbb S|-1}$,这相当于什么?若 $t\mid\mathbb S$,则 $\mathbb S$ 中的每个元素都是 $t$ 的倍数;换言之,如果 $t\mid a_k$,$a_k$ 就可以成为 $\mathbb S$ 的元素。
所以预处理出 $c_t$ 表示有多少个 $a_k$ 满足 $t\mid a_k$,则满足 $t\mid\mathbb S$ 的 $\mathbb S$ 一定是这 $c_t$ 个元素的子集。
$h(t)$ 相当于计算“大小为奇数的 $\mathbb S$ 的数量-大小为偶数的 $\mathbb S$ 的数量”。
- 若在 $c_t$($c_t\ge 1$)个元素构成的集合任意取子集(包括空集),奇数集的个数等于偶数集的个数,但是现在不能取空集,所以偶数集个数减一,$h(t)=1$;
- 若 $c_t=0$,则 $h(t)=0$。
即 $h(t)=[c_t>0]$。
继续推原来的式子:
这样就可以计算了。具体地说,先 $O(n\sqrt{a_i})$ 处理出 $c_t$,从而可以得到 $h(t)=[c_t>0]$;然后线性筛出 $\mu$;计算答案则直接暴力枚举 $d,t$,是调和级数的复杂度。
# 源代码
1 | /*Lucky_Glass*/ |