题目分析

首先有一个结论：$gcd(fib(a_i))= fib(gcd(a_i))$，可以尝试使用辗转相减球 gcd 的方法证明一下。（boshi: 可以证，但没必要）

然后 $lcm$是个什么玩意呢？对于一个指定的质因数 $p$，假设 $a_i$的质因数 $p$的次数为 $c_i$，则他们的 lcm 的 $p$的次数为 $max(c_i)$，gcd 的 $p$的次数为 $min(c_i)$。看到这里，可以考虑 Max-Min 容斥（又称 Max-Min 反演），最后可以得到：

$$lcm(fib(S))=\prod_{T \subset S,T \not= \emptyset} fib(gcd(T))^{(-1)^{|T|+1}}$$

假设 $fib(x)$的正数幂大小为 $c_1$，负数幂绝对值大小为 $c_2$，则我们只要把所有 $fib(x)^{c_1-c_2}$乘起来即可。

怎么求呢？以求 $c_1$为例，只要用 $O(n \ln n)$的时间求出 $x$的倍数有多少个，则知 $gcd$是 $x$的倍数，且集合大小为奇数的集合有多少个，设为 $f(x)$个。设 $gcd$是 $x$且集合大小为奇数的集合有 $g(x)$个，则有：

$$f(x)=\sum_{x|d} g(d)$$

莫比乌斯反演一下：

$$g(x)=\sum_{x|d} \mu(\frac{x}{d})f(d)$$

求 $g(x)$也是 $O(n \ln n)$的，完美！

代码

#include<bits/stdc++.h>
using namespace std;
#define RI register int
int read() {
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
    return q;
}
const int mod=1000000007,N=1000000;
int n,tot,ans=1;
int a[N+5],b[N+5],f[N+5],mu[N+5],pri[N+5],is[N+5],c[N+5];

int ksm(int x,int y,int p) {
    int re=1;
    for(;y;y>>=1,x=1LL*x*x%p) if(y&1) re=1LL*re*x%p;
    return re;
}
void prework() {
    f[1]=1;for(RI i=2;i<=N;++i) f[i]=(f[i-1]+f[i-2])%mod;
    for(RI i=1;i<=N;++i)
        for(RI j=i;j<=N;j+=i) b[i]=b[i]+a[j];
    mu[1]=1;
    for(RI i=2;i<=N;++i) {
        if(!is[i]) pri[++tot]=i,mu[i]=-1;
        for(RI j=1;j<=tot&&pri[j]*i<=N;++j) {
            is[pri[j]*i]=1;
            if(i%pri[j]==0) break;
            else mu[pri[j]*i]=-mu[i];
        }
    }
}
void getc1() {
    for(RI i=1;i<=N;++i) if(b[i]) b[i]=ksm(2,b[i]-1,mod-1);
    for(RI i=1;i<=N;++i)
        for(RI j=i;j<=N;j+=i)
            c[i]=(1LL*c[i]+1LL*mu[j/i]*b[j]+mod-1)%(mod-1);
}
void getc2() {
    for(RI i=1;i<=N;++i) if(b[i]) --b[i];
    for(RI i=1;i<=N;++i)
        for(RI j=i;j<=N;j+=i)
            c[i]=(1LL*c[i]-1LL*mu[j/i]*b[j]+mod-1)%(mod-1);
    for(RI i=1;i<=N;++i) c[i]=(c[i]+mod-1)%(mod-1);
}

int main()
{
    n=read();
    for(RI i=1;i<=n;++i) ++a[read()];
    prework();
    getc1(),getc2();
    for(RI i=1;i<=N;++i) ans=1LL*ans*ksm(f[i],c[i],mod)%mod;
    printf("%d\n",ans);
    return 0;
}