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

题目描述

斐波那契数列定义如下：

F(0) = 0 F(1) = 1

F(n) = F(n-1) + F(n-2)

给出n个正整数a1, a2,…… an，求对应的斐波那契数的最小公倍数，由于数字很大，输出Mod 1000000007的结果即可。

例如：1 3 6 9, 对应的斐波那契数为：1 2 8 34, 他们的最小公倍数为136。

输入

第1行：1个数N，表示数字的数量（2 <= N <= 50000）。

第2 至 N + 1行：每行1个数，对应ai。（1 <= ai <= 1000000)。

输出

输出Lcm(F(a1), F(a2) …… F(an)) Mod 1000000007的结果。

样例输入

样例输出

136

题解

首先做这个题要知道一个斐波那契数列的性质，我们用\(F_i\)来表示斐波那契数列第i项，那么有\(\gcd (F_a, F_b) = F_{\gcd (a,b)}\)。而lcm没有像gcd那样优美的性质。

如果你熟悉min-max容斥那一套理论，很容易就能发现可以用gcd荣吃出lcm啦，但是如果你不熟悉呢？

把gcd的过程想象成求质因子k次幂交，lcm的过程想象成求质因子k次幂并，那么我们把若干个集合的交，通过容斥原理凑出来并集。

即\(\max \{a_i\} = \sum_{S \in \{a_i\}} \min \{a_S\} * (-1) ^ {|S| + 1}\)

根据这个我们可以发现一些数字的lcm可以由他们子集gcd推出来。

我们要算的其实是\(\prod_{S \in \{a_i\}} F_{\gcd \{S\}}^{(-1)^{|S|+1}}\)

令\(F_n = \prod_{d|n} g_d\)

做一次反演得到\(\prod_d g_d^{\sum_{S \in \{a_i\}} (-1)^{|S|+1}}\)

观察这个式子，S不能为空集，因此如果存在一个\(a_i\)使得\(d|a_i\)那么那个指数为1（考虑空集为0），否则那个指数为0（考虑空集为-1）。

那么就很好做了，对于g我们可以反演暴力求，答案也暴力求就可以了。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int P = 1000000007;
const int maxn = 50005;
bool v[1000005], vis[1000005];
int n, ans = 1, cnt, a[maxn], f[1000005], g[1000005];
int ksm(int a, int b, int c) {
    int r = 1, t = a;
    while (b) {
        if (b & 1) r = (LL) r * t % P;
        t = (LL) t * t % P;
        b >>= 1;
    }
    return r;
}
void solve(int x) {
    int gg = ksm(g[x], P - 2, P);
    v[x] = vis[x];
    for (int i = x + x; i <= 1000000; i += x) {
        v[x] |= vis[i];
        g[i] = (LL) g[i] * gg % P;
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        vis[a[i]] = true;
    }
    f[1] = g[1] = 1;
    for (int i = 2; i <= 1000000; ++i) f[i] = g[i] = (f[i-1] + f[i-2]) % P;
    for (int i = 1; i <= 1000000; ++i) { solve(i); if (v[i]) ans = (LL) ans * g[i] % P; }
    printf("%d", ans);
}