没啥意思的板子题。
首先，众所周知，
[gcd{f_a,f_b}=f_{gcd{a,b}}
]
所以考虑将 (operatorname{lcm}) 转化为 (gcd)。
(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) 反演）
于是只用计算每个 (v=gcdlimits_{ain T}a)，其 (v) 的幂次的贡献。
考虑到这需要 (gcd) 卷积。
不妨设有全集 (U)，满足其为所有（考虑范围内的）数的倍数。
这样，我们即可用 (gcd) 卷积描述其为
[z^U-prod_{ain S}^{gcdtext{卷积}}(z^U-z^a)
]
众所周知这个形式可以使用 CF449D 的技巧，用 Dirichlet 前缀和可以对其优化。
然后就做完了。
核心代码很短。
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;
}
程序员灯塔
转载请注明原文链接：51nod1355
转载请注明原文链接：51nod1355