Always Firmly on OI

【51nod 1355】 斐波那契的最小公倍数

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)}$$

之后就要去看一下斐波那契数列的性质咯

通过 这道题 可以学习到一个关于斐波那契数列的很重要的性质:

$$\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$ 的贡献(注意最多产生一次)

代码

#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);
}