正题

题目链接:http://www.51nod.com/Challenge/Problem.html#problemId=1355

---

题目大意

定义 f i f_i fi​表示斐波那契的第 i i i项，给出一个大小为 n n n的集合 S S S求 l c m ( f S ) lcm(f_S) lcm(fS​)

---

解题思路

如果每个质数的次数分开考虑，那么 g c d gcd gcd就是次数取 m i n min min， l c m lcm lcm就是次数取 m a x max max，所以可以套用 m i n − m a x min-max min−max容斥的式子
l c m ( S ) = ∏ T ⊆ S g c d ( T ) ( − 1 ) ∣ T ∣ + 1 lcm(S)=\prod_{T\subseteq S}gcd(T)^{(-1)^{|T|+1}} lcm(S)=T⊆S∏​gcd(T)(−1)∣T∣+1
然后因为 g c d ( f x , f y ) = f g c d ( x , y ) gcd(f_x,f_y)=f_{gcd(x,y)} gcd(fx​,fy​)=fgcd(x,y)​，那么这题的答案
l c m ( f S ) = ∏ T ⊆ S f g c d ( T ) ( − 1 ) ∣ T ∣ + 1 lcm(f_S)=\prod_{T\subseteq S}f_{gcd(T)}^{(-1)^{|T|+1}} lcm(fS​)=T⊆S∏​fgcd(T)(−1)∣T∣+1​
这个好像算起来很麻烦，我们可以分开考虑每个 g c d gcd gcd的贡献。
定义 f n = ∏ d ∣ n g d f_n=\prod_{d|n}g_d fn​=∏d∣n​gd​
l c m ( f S ) = ∏ T ⊆ S ( ∏ d ∣ g c d ( T ) g d ) ( − 1 ) ∣ T ∣ + 1 lcm(f_S)=\prod_{T\subseteq S}\left(\prod_{d|gcd(T)}g_d\right)^{(-1)^{|T|}+1} lcm(fS​)=T⊆S∏​⎝⎛​d∣gcd(T)∏​gd​⎠⎞​(−1)∣T∣+1
l c m ( f S ) = ∏ g d ∑ T ⊆ S [ d ∣ g c d ( T ) ] ( − 1 ) ∣ T ∣ + 1 lcm(f_S)=\prod g_d^{\sum_{T\subseteq S}[d|gcd(T)](-1)^{|T|+1}} lcm(fS​)=∏gd∑T⊆S​[d∣gcd(T)](−1)∣T∣+1​
然后就是 ∑ T ⊆ S [ d ∣ g c d ( T ) ] ( − 1 ) ∣ T ∣ + 1 \sum_{T\subseteq S}[d|gcd(T)](-1)^{|T|+1} ∑T⊆S​[d∣gcd(T)](−1)∣T∣+1，因为没有了空集，这个东西其实就相当于 [ ∃ a i ∈ S , d ∣ a i ] [\exists a_i\in S,d|a_i] [∃ai​∈S,d∣ai​]。然后就可以直接枚举每个 d d d来求答案了。
l c m ( f S ) = ∏ ∃ a i ∈ S , d ∣ a i g d lcm(f_S)=\prod_{\exists a_i\in S,d|a_i} g_d lcm(fS​)=∃ai​∈S,d∣ai​∏​gd​

考虑 g g g怎么构造，我们有 f n = ∏ d ∣ n g d f_n=\prod_{d|n}g_d fn​=∏d∣n​gd​，直接移项就是 g n = f n − ∏ d ∣ n , d ≠ n g d g_n=f_n-\prod_{d|n,d\neq n}g_d gn​=fn​−∏d∣n,d​=n​gd​就好了。

时间复杂度 O ( n log ⁡ n ) O(n\log n) O(nlogn)

---

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll N=1e6+10,P=1e9+7;
ll n,m,g[N],ans;
bool v[N];
ll power(ll x,ll b){
    ll ans=1;
    while(b){
        if(b&1)ans=ans*x%P;
        x=x*x%P;b>>=1;
    }
    return ans;
}
signed main()
{
    scanf("%lld",&n);g[1]=ans=1;
    for(ll i=1;i<=n;i++){
        ll x;scanf("%lld",&x);
        m=max(m,x);v[x]=1;
    }
    for(ll i=2;i<=m;i++)g[i]=(g[i-1]+g[i-2])%P;
    for(ll i=1;i<=m;i++){
        ll inv=power(g[i],P-2);
        for(ll j=2*i;j<=m;j+=i)
            g[j]=g[j]*inv%P;
    }
    for(ll i=1;i<=m;i++){
        bool flag=0;
        for(ll j=i;j<=m;j+=i)
            if(v[j]){flag=1;break;}
        if(flag)ans=(ans*g[i])%P;
    }
    printf("%lld\n",ans);
    return 0;
}