【51nod 1355】 斐波那契的最小公倍数
nekko
2018-12-25 10:03:45
### 题目描述
设 $f_0=0,f_1=1$，且 $\forall i \ge 2$，有 $f_i=f_{i-1}+f_{i-2}$
给定 $n$，以及一个长度为 $n$ 的数组 $a$
求：
$$\text{lcm}(f_{a_1},f_{a_2},f_{a_3},f_{a_4},\cdots,f_{a_n}) \bmod {1000000007}$$
$2 \le n \le 50000$
$1 \le a_i \le 10^6$
### 题解
不妨手玩一下关于 $\text{lcm}$ 的性质……
$$\text{lcm}(a,b)=\frac{ab}{\gcd(a,b)}$$
$$\text{lcm}(a,b,c)=\frac{abc\gcd(a,b,c)}{\gcd(a,b)\gcd(b,c)\gcd(a,c)}$$
推广到更一般的情况，即一个集合 $S$ 的 $\text{lcm}$：
$$\text{lcm}(S)=\prod_{\emptyset \ne T \subseteq S} \gcd(T)^{\left( (-1)^{\mid T \mid + 1} \right)}$$
之后就要去看一下斐波那契数列的性质咯
通过 [这道题](https://www.luogu.org/problemnew/show/P1306) 可以学习到一个关于斐波那契数列的很重要的性质：
$$\gcd(f_i,f_j)=f_{\gcd(i,j)}$$
于是就可以化简一下式子咯：
$$ \begin{aligned} &\text{lcm}(f_{a_1},f_{a_2},f_{a_3},f_{a_4},\cdots,f_{a_n}) \\ =&\prod_{\emptyset \ne T \subseteq S} \gcd({f_{T}})^{\left( (-1)^{\mid T \mid + 1} \right)} \\ =&\prod_{\emptyset \ne T \subseteq S} f_{\gcd(T)}^{\left( (-1)^{\mid T \mid + 1} \right)} \\ \end{aligned} $$
然而这个还是不太好做……因为有一个 $[\gcd(S)=d]$ 的限制……
然而这个可以想到莫比乌斯反演那一套理论
$$f=g \times 1 \Leftrightarrow g=f \times \mu$$
考虑在 $\prod$ 意义下的莫比乌斯反演……
$$f_n=\prod_{d \mid n} g_d \Leftrightarrow g_n=\prod_{d \mid n}f_d^{\mu(\frac{n}{d})}$$
当然如果只是要计算 $g$的话，有：
$$f_n=\prod_{d \mid n} g_d \Rightarrow g_n=\frac{f_n}{\prod_{d \mid n \wedge d \ne n}g_d}$$
然后就可以通过枚举倍数来计算出 $g$ 了
于是现在式子就相当于这个了：
$$ \begin{aligned} &\prod_{\emptyset \ne T \subseteq S} f_{\gcd(T)}^{\left( (-1)^{\mid T \mid + 1} \right)} \\ =&\prod_{\emptyset \ne T \subseteq S} \left(\prod_{d \mid \gcd(T)}g_d\right)^{\left( (-1)^{\mid T \mid + 1} \right)} \\ =&\prod_{d} g_d^{\sum_{\emptyset \ne T \subseteq S \wedge d \mid \gcd(T)}(-1)^{\mid T \mid + 1}} \end{aligned} $$
考虑一个 $g_d$ 对答案的贡献，也就是指数上那个玩意，即：
$$\sum_{\emptyset \ne T \subseteq S \wedge d \mid \gcd(T)} (-1)^{\mid T \mid +1}$$
显然是实际有用的 $T$ 的并集是 $S'=\{x \mid \forall x \in S \wedge d \mid x\}$
假设 $\mid S' \mid = n$，则有：
$$ \begin{aligned} &\sum_{\emptyset \ne T \subseteq S \wedge d \mid \gcd(T)} (-1)^{\mid T \mid +1} \\ =&\sum_{i=1}^{n} {n \choose i} (-1)^{i+1} \\ =&(-1) \left(\sum_{i=1}^{n}{n \choose i}(-1)^{i}\right) \\ =&(-1) \left((1-1)^n-{n \choose 0} (-1)^{0}\right) \\ =&[n \ne 0] \end{aligned} $$
也就是说，对于一个 $g_d$，只要 $\exists x \mid a_i$，那么 $g_d$ 就会对答案产生 $1$ 的贡献（注意最多产生一次）
### 代码
``` cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10, mod = 1e9 + 7;
int n, mx, a[N]; ll fib[N], g[N], cnt[N], ans = 1;
ll pw(ll a, ll b) {
ll r = 1;
for( ; b ; b >>= 1, a = a * a % mod)
if(b & 1)
r = r * a % mod;
return r;
}
int main() {
scanf("%d", &n);
for(int i = 1 ; i <= n ; ++ i) scanf("%d", &a[i]), mx = max(mx, a[i]), cnt[a[i]] ++;
fib[1] = g[1] = 1; for(int i = 2 ; i <= mx ; ++ i) g[i] = fib[i] = (fib[i - 1] + fib[i - 2]) % mod;
for(ll i = 1 ; i <= mx ; ++ i)
for(ll j = 2, inv = pw(g[i], mod - 2) ; i * j <= mx ; ++ j)
g[i * j] = g[i * j] * inv % mod;
for(ll i = 1 ; i <= mx ; ++ i)
for(ll j = 1 ; i * j <= mx ; ++ j)
if(cnt[i * j]) {
ans = ans * g[i] % mod;
break;
}
printf("%lld\n", (ans % mod + mod) % mod);
}
```