51nod

LOJ

分析

为了方便，下面简记 $f_S$ 为 $f_{a_1},f_{a_2},\cdots,f_{a_k}$，其中 $S=\{a_1,a_2,\cdots,a_k\}$。

考虑一个经典容斥
$$
\operatorname{lcm}(f_S)=\prod_{T\subseteq S,T\neq\varnothing}\gcd(f_T)^{(-1)^{|T|+1}}
$$
证明可以考虑对每个质因子的质数 min-max 容斥。

因为 $\gcd(f_T)=f_{\gcd(T)}$，所以
$$
\operatorname{lcm}(f_S)=\prod_{T\subseteq S,T\neq\varnothing}f_{\gcd(T)}\!^{(-1)^{|T|+1}}
$$
考虑构造一个数列 $\{g_n\}$ 满足 $f_n=\prod_{d|n}g_n$（先不考虑如何构造），那么上式可以改写为
$$
\operatorname{lcm}(f_S)=\prod_{T\subseteq S,T\neq\varnothing}\left(\prod_{d|\gcd(T)}g_d\right)^{(-1)^{|T|+1}}
$$
即
$$
\operatorname{lcm}(f_S)=\prod_{d\geq 1}g_d\!^{\sum_{T\subseteq S,T\neq\varnothing,d|T}(-1)^{|T|+1}}
$$
考虑 $g_d$ 指数的取值，不难发现
$$
\sum_{T\subseteq S,T\neq\varnothing,d|T}(-1)^{|T|+1}=\begin{cases}1,&\left\lvert\left\{a|a\in S,d|a\right\}\right\rvert\neq 0\\0,&\mathrm{otherwise}\end{cases}
$$
于是上式继续化简为
$$
\operatorname{lcm}(f_S)=\prod_{\exists a\in S,d|a}g_d
$$
现在考虑如何构造 $\left\{g_n\right\}$。直接移项可以得到
$$
g_n=f_n\left(\prod_{d|n,d\neq n}g_d\right)^{-1}
$$
从小到大枚举倍数算贡献即可。

实现得好的话时间复杂度是 $\mathcal{O}(n\log n)$ 的。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1000000+10;
const int mod=1e9+7;
int qpow(int a,int b) { int c=1;
    for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
    return c;
}

int n,a[N],vis[N],f[N],g[N];

int main() {
    n=read(); int L=0;
    for (int i=1;i<=n;++i) a[i]=read(),L=max(L,a[i]);
    for (int i=1;i<=n;++i) vis[a[i]]=1;
    f[1]=1;
    for (int i=2;i<=L;++i) f[i]=(f[i-1]+f[i-2])%mod;
    for (int i=1;i<=L;++i) g[i]=f[i];
    for (int i=1;i<=L;++i) {
        int t=qpow(g[i],mod-2);
        for (int j=i+i;j<=L;j+=i) g[j]=1ll*g[j]*t%mod;
    }
    int ans=1;
    for (int i=1;i<=L;++i) {
        int flag=0;
        for (int j=i;j<=L;j+=i) if (vis[j]) { flag=1; break; }
        if (flag) ans=1ll*ans*g[i]%mod;
    }
    printf("%d\n",ans);
    return 0;
}