51Nod1355 斐波那契的最小公倍数 < Min-Max容斥 >

Problem

斐波那契的最小公倍数

Description

斐波那契数列定义如下：

给出个正整数，求对应的斐波那契数的最小公倍数，由于数字很大，输出模的结果即可。
例如：, 对应的斐波那契数为：, 他们的最小公倍数为。

Input

第行个数，表示数字的数量。（）。
第至行每行个数，对应。（)。

Output

输出的结果。

Input示例

Output示例

标签：Min-Max容斥

Solution

烂大街的套路题，我居然没见过。
%%%张一钊
以下内容均转载自某乎。

因为是斐波那契数列，有。
由容斥可得。
于是。
构造，使得，则。
即有。
考虑的指数的意义，可知

因而，若知道可在时间内计算（为值域即）。
将定义式中的单独拿出来，有，时间复杂度由于是调和级数也为。
总复杂度。

Code

#include <bits/stdc++.h>
#define MX 1000000
#define P 1000000007
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n; bool mrk[MX+5];
lnt f[MX+5], g[MX+5];
lnt inv(lnt x) {
    lnt k = P-2, ret = 1;
    for (; k; k >>= 1, x = x*x%P)
        if (k&1) ret = ret*x%P;
    return ret;
}
void init() {
    f[1] = f[2] = g[1] = g[2] = 1;
    for (int i = 3; i <= MX; i++)
        f[i] = g[i] = (f[i-2]+f[i-1])%P;
    for (int i = 1; i <= MX; i++) {
        lnt invg = inv(g[i]);
        for (int j = i+i; j <= MX; j += i)
            g[j] = g[j]*invg%P;
    }
}
int main() {
    read(n), init(); lnt ans = 1;
    for (int i = 1, x; i <= n; i++)
        read(x), mrk[x] = true;
    for (int i = 1; i <= MX; i++) {
        bool flag = false;
        for (int j = i; j <= MX; j += i)
            if (mrk[j]) {flag = true; break;}
        if (flag) ans = ans*g[i]%P;
    }
    return printf("%lld\n", ans), 0;
}