Description
给定 (n) 个正整数 (a_1,a_2,...,a_n)，求 ( ext{lcm}(f_{a_1},f_{a_2},...,f_{a_n}))。其中 (f_i) 是斐波那契数列第 (i) 项。 (nleq 50000,a_ileq 10^6)。
Sol
首先关于集合 (S) 的( ext{lcm})可以用类似( ext{min-max})容斥的式子搞一下，变成跟(gcd)有关：
[ ext{lcm}(T)=prod_{Ssubseteq T} gcd(S)^{left((-1)^{|S|+1}
ight)}
]
所以原式就可以变成：
[ ext{lcm}(f_{{T}})=prod_{Ssubseteq T} (f_{gcd{S}})^{left((-1)^{|S|+1}
ight)}
]
看见这个(gcd)想到莫比乌斯反演
设：
[f_n=prod_{dmid n} g_d
]
那么：
[g_n=frac{f_n}{prodlimits_{dmid nland d
e n} g_d}
]
所以原式化为：
[egin{aligned}
ext{lcm}(f_{{T}})&=prod_{Ssubseteq T}left(prod_{dmid gcd(S)} g_d
ight) ^{left((-1)^{|S|+1}
ight)}\
&= prod_{d} g_d^{;;sumlimits_{Ssubseteq Tland dmid gcd(S)} (-1)^{|T|+1}}
end{aligned}
]
然后看看这个式子等于什么：
[sumlimits_{Ssubseteq Tland dmid gcd(S)} (-1)^{|T|+1}
]
把所有在 (T) 中且是 (d) 的倍数的 (x) 扔进一个新集合 (S') 中，设(|S'|=n)，那么：
[egin{aligned}
&sumlimits_{Ssubseteq Tland dmid gcd(S)} (-1)^{|T|+1}\
=&sum_{i=1}^n {nchoose i} (-1)^{i+1}\
=&(-1)left(sum_{i=1}^n {nchoose i}(-1)^i
ight)\
=&(-1)left( (1-1)^n-1
ight)\
=&epsilon(n
eq 0)
end{aligned}
]
也就是说，只要有一个元素是 (d) 的倍数，那么 (g_d) 就有贡献。
Code
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
typedef double db;
typedef long long ll;
const int N=1e6+5;
const int mod=1e9+7;
int n,mx,a[N],f[N],g[N];
int ksm(int a,int b=mod-2,int ans=1){
while(b){
if(b&1) ans=1ll*ans*a%mod;
a=1ll*a*a%mod;b>>=1;
} return ans;
}
void init(int n){
f[1]=1;
for(int i=2;i<=n;i++)
f[i]=(f[i-1]+f[i-2])%mod;
for(int i=1;i<=n;i++)
for(int j=i+i,p=ksm(f[i]);j<=n;j+=i)
f[j]=1ll*f[j]*p%mod;
}
signed main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]),mx=max(mx,a[i]),g[a[i]]=1;
init(mx); int ans=1;
for(int i=1;i<=mx;i++)
for(int j=i;j<=mx;j+=i)
if(g[j]){
ans=1ll*ans*f[i]%mod;
break;
}
printf("%d
",ans); return 0;
}