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

Problem

斐波那契的最小公倍数

$\mathrm{Time\;Limit:\;3\;Sec}$
$\mathrm{Memory\;Limit:\;131072\;KB}$

Description

斐波那契数列定义如下：

$$F(0) = 0\\ F(1) = 1\\ F(n) = F(n-1) + F(n-2)\\$$

给出$n$个正整数$a_1, a_2,\cdots a_n$，求对应的斐波那契数的最小公倍数，由于数字很大，输出模 $1000000007$的结果即可。
例如：$\lbrace1,3,6,9\rbrace$, 对应的斐波那契数为：$\lbrace1,2,8,34\rbrace$, 他们的最小公倍数为$136$。

Input

第$1$行$1$个数$N$，表示数字的数量。（$2\le N\le50000$）。
第$2$至$N+1$行每行$1$个数，对应$a_i$。（$1\le a_i\le1000000$)。

Output

输出$\mathrm{lcm}(F(a_1),F(a_2),\cdots,F(a_n))\bmod{1000000007}$的结果。

Input示例

4
1
3
6
9

Output示例

136

标签：Min-Max容斥

Solution

烂大街的套路题，我居然没见过QAQ。

以下内容均转载自某乎（张一钊）。

因为是斐波那契数列，有$\gcd(f_p,f_q)=f_{\gcd(p,q)}$。
由$\mathrm{Min-Max}$容斥可得$\mathrm{lcm}\lbrace S\rbrace=\prod_{T\subseteq S,T\ne\emptyset}\gcd\lbrace T\rbrace^{(-1)^{|T|+1}}$。
于是$\mathrm{lcm}\lbrace f_S\rbrace=\prod_{T\subseteq S,T\ne\emptyset}f_{\gcd\lbrace T\rbrace}^{(-1)^{|T|+1}}$。
构造$\lbrace g\rbrace$，使得$f_n=\prod_{d|n}g_d$，则$\mathrm{lcm}\lbrace f_S\rbrace=\prod_{T\subseteq S,T\ne\emptyset}\prod_{d|\gcd\lbrace T\rbrace}g_d^{(-1)^{|T|+1}}$。
即有$\mathrm{lcm}\lbrace f_S\rbrace=\prod_d g_d^{\sum_{T\subseteq S,T\ne\emptyset,d|T}(-1)^{|T|+1}}$。
考虑$g_d$的指数的意义，可知

$$\sum_{T\subseteq S,T\ne\emptyset,d|T}(-1)^{|T|+1}= \begin{cases} 1&|\lbrace a|a\in S,d|a\rbrace|>0\\ 0&\text{otherwise} \end{cases}$$

因而$\mathrm{lcm}\lbrace f_S\rbrace=\prod_{\exists a\in S,d|a}g_d$，若知道可在$\mathcal{O}(R\log{R})$时间内计算（$R$为值域即$\max\lbrace S\rbrace$）。
将$g$定义式中的$g_n$单独拿出来，有$g_n=f_n\cdot(\prod_{d|n,d\ne n}g_d)^{-1}$，时间复杂度由于是调和级数也为$\mathcal{O}(R\log{R})$。
总复杂度$\mathcal{O}(R\log{R})$。

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