题意简化

给定 $n$ 个数 $k_1, k_2, ..., k_n$，求：

$$LCM(f(k_1), f(k_2), ..., f(k_n)) \bmod 10^9+7$$

其中 $f(i)$ 是斐波那契数列：$f(0)=0, f(1)=1, f(i)=f(i-1)+f(i-2)$。

$n \le 5\times 10^4$，$k_i \le 10^6$。

核心思想：数论性质 + 容斥

1. 斐波那契数列的性质

关键性质：

• $\gcd(f(a), f(b)) = f(\gcd(a, b))$
• 由这个性质可以推导出 LCM 的表达式

2. LCM 公式推导

对于数列 $f(k_1), f(k_2), ..., f(k_n)$，有：

$$LCM(f(k_1), f(k_2), ..., f(k_n)) = \prod_{d=1}^{\max(k_i)} f(d)^{c_d} $$

其中指数 $c_d$ 由包含因子 $d$ 的 $k_i$ 决定。

更具体地，利用莫比乌斯反演：

$$f(n) = \prod_{d|n} g(d)$$

其中 $g(d)$ 是某个函数。

反过来：

$$g(n) = \prod_{d|n} f(d)^{\mu(n/d)}$$

3. 代码算法解析

预处理部分：

1. 线性筛：计算莫比乌斯函数 $\mu(i)$
2. 斐波那契数列：计算 $f(i)$ 模 $10^9+7$
3. 计算 $g(i)$：使用公式 $g(n) = \prod_{d|n} f(d)^{\mu(n/d)}$

代码实现巧妙：

// 初始化 g[i] = f[i]
for (int i = 1; i <= n; i++) g[i] = f[i];

// 通过除法计算 g
for (int i = 1; i <= n; i++) {
    int t = qpow(g[i], mod-2);  // g[i] 的逆元
    for (int j = i+i; j <= n; j += i)
        g[j] = g[j] * t % mod;
}

这等价于：$g[j] = \prod_{d|j} f(d)^{\mu(j/d)}$

主计算部分：

1. 读入 $k_i$，标记 p[k_i] = true
2. 对于每个 $i$，检查是否存在 $k_j$ 是 $i$ 的倍数
3. 如果存在，则将 $g[i]$ 乘入答案

为什么这样正确？

• $g(i)$ 表示斐波那契数 $f$ 的某种"本原"因子
• 如果存在 $k_j$ 是 $i$ 的倍数，那么 $f(i)$ 会"贡献"到 $f(k_j)$ 的质因子分解中
• 求 LCM 时需要包含所有 $g(i)$，其中 $i$ 能整除至少一个 $k_j$

算法步骤

1. 预处理（到 $10^6$）：

   • 线性筛 $\mu(i)$
   • 计算 $f(i)$ 模 $mod$
   • 计算 $g(i) = \prod_{d|i} f(d)^{\mu(i/d)}$

2. 读入处理：

   • 记录最大的 $k_i$ 为 $mx$
   • 标记哪些 $k$ 值出现过

3. 计算答案：

   ans = 1
   for i = 1 to mx:
       flag = false
       for j = i; j <= mx; j += i:
           if p[j]:
               flag = true
               break
       if flag:
           ans = ans * g[i] % mod
   

复杂度分析

• 预处理：$O(M \log M)$，$M=10^6$
• 标记 $k_i$：$O(n)$
• 计算答案：每个 $i$ 检查倍数，总复杂度 $O(M \log M)$
• 可过 $M=10^6$

关键点

1. 数论公式

$$LCM(f(k_1),...,f(k_n)) = \prod_{d} g(d)^{[\exists k_i \text{是} d \text{的倍数}]} $$

2. $g$ 的计算

$g$ 是 $f$ 的莫比乌斯反演，表示"本原"因子。

3. 倍数检查

只需检查是否存在 $k_i$ 是 $d$ 的倍数，不需要统计个数。

样例解释

输入：$k = [1, 3, 9, 6]$

斐波那契值：

• $f(1)=1$
• $f(3)=2$
• $f(6)=8$
• $f(9)=34$

LCM = LCM(1,2,8,34) = 136

代码特点

• 预处理到 $10^6$（最大 $k_i$）
• 使用莫比乌斯反演
• 逆元优化 $g$ 的计算
• 倍数标记检查