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的结果。

样例输入

4
1
3
6
9

样例输出

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我们可以反演暴力求,答案也暴力求就可以了。

代码

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

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据