• 欢迎光临~

# 51nod1355

[gcd{f_a,f_b}=f_{gcd{a,b}} ]

(min-max) 容斥指出，

[max_{ain S}a=sum_{Tsubseteq S,Tneqvarnothing}(-1)^{|T|-1}min_{ain T}a ]

[mathop{operatorname{lcm}}limits_{ain S}a=prod_{Tsubseteq S,Tneqvarnothing}(gcd_{ain T}a)^{(-1)^{|T|-1}} ]

（对每个质因子做一次 (min-max) 反演）

[z^U-prod_{ain S}^{gcdtext{卷积}}(z^U-z^a) ]

``````const ullt Mod=1e9+7;
typedef ConstMod::mod_ullt<Mod>modint;
typedef std::vector<modint>modvec;
int Cnt[2000005];
bol Gone[2000005];
modint F[2000005];
int main()
{
#ifdef MYEE
freopen("QAQ.in","r",stdin);
// freopen("QAQ.out","w",stdout);
#endif
uint n;scanf("%u",&n);
for(uint i=0,v;i<n;i++)
scanf("%u",&v),Cnt[v]++;
for(uint i=2;i<=1000000;i++)if(!Gone[i]){
for(uint j=1000000/i*i;j;j-=i)
Cnt[j/i]+=Cnt[j],Gone[j]=1;
Gone[i]=0;
}
F[1]=1;
for(uint i=1;i<=1000000;i++)
Cnt[i]=(bol)Cnt[i],F[i+1]=F[i]+F[i-1];
for(uint i=2;i<=1000000;i++)if(!Gone[i])
for(uint j=i;j<=1000000;j+=i)
Cnt[j/i]-=Cnt[j];
modint ans(1);
for(uint i=1;i<=1000000;i++)
ans*=Cnt[i]>=0?F[i]^Cnt[i]:F[i]^(((Mod-2)*-Cnt[i])%(Mod-1));
ans.println();
return 0;
}
``````