【Codeforces 585E】Present for Vitalik the Philatelist
莫比乌斯反演，狄利克雷前/后缀和
题目大意：
给定 $n$ 个数 $a_1,a_2,a_3,\dots,a_n$，每个数在 $[2,10^7]$ 之间。
现在要选择一个下标集合 $S$ 和一个下标 $x$，满足：$x\not\in S;\gcd_{i\in S}\{a_{i}\}>1;\gcd(x,\gcd_{i\in S}\{a_{i}\})=1$。
求满足条件的 $(S,x)$ 的个数。
题解：
我数学是真的菜啊
令 $s_n$ 表示最大公因数恰好为 $n$ 的集合个数，$f_n$ 表示与 $n$ 互质的数的个数。
那么我们要求的就是 $\sum_i s_if_i$.
考虑求出 $s$ 和 $f$。
考虑计算 $f_i$。令 $c_i$ 表示数 $i$ 的出现次数。
强行莫比乌斯反演qwq
我们令 $g_k=\sum\limits_{k|i}c_i$；$g’_k=\mu(k)g_k$，那么 $f_n=\sum\limits_{d|n} g’_d$
发现这个 $g_i$ 就表示 $i$ 的倍数的出现次数。
再考虑求 $s_i$。我们令 $s’_i$ 表示最大公因数为 $i$ 的倍数的方案数。要使最大公因数为 $i$ 的倍数，那么每个选的数必须是 $i$ 的倍数。所以容易得到 $s’_i=2^{g_i}-1$
我们又有 $s’_i=\sum\limits_{i|d}s_d$
观察上面的式子的形式，他们都是这样的形式：
其中，上面的式子为狄利克雷前缀和，下面的式子为狄利克雷后缀和。
这两个东西，都可以在 $O(w\log\log w)$ 的时间复杂度内完成。具体做法请见我贡献的【模板】Dirichlet 前缀和（后缀和与前缀和的做法本质相同，都是高维前缀和）。
计算 $g$ 和 $f$ 都是标准的狄利克雷前/后缀和形式。
但还有个问题，已知 $a$ 求 $b$ 能做了，但是那个 $s$ 的计算，是已知 $b$ 求 $a$ 的。
前面是加，那现在就把它逆回去就好了。具体就是把两重循环的反向，然后把加法改成减法就可以辣。当然也可以用高维前缀和的知识解释。
总时间复杂度 $O(n+w\log\log w)$。
Code：
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=5e5+5,M=1e7+2,md=1e9+7;
int S[M],_2[500005],a[500005],tot[M],g[M],pri[M/10],cnt,mu[M];
bool vis[M];
inline void upd(int&a){a+=a>>31&md;}
int n,lim,ans;
void sieve(const int n){
mu[1]=1;
for(int i=2;i<=n;++i){
if(!vis[i])pri[++cnt]=i,mu[i]=-1;
for(int j=1;j<=cnt&&i*pri[j]<=n;++j){
vis[i*pri[j]]=1;
if(i%pri[j]==0){
mu[i*pri[j]]=0;
break;
}else mu[i*pri[j]]=-mu[i];
}
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
for(int i=*_2=1;i<=500000;++i)upd(_2[i]=_2[i-1]*2-md);
cin>>n;
for(int i=1;i<=n;++i)
cin>>a[i],++tot[a[i]];
lim=*max_element(a+1,a+n+1);
sieve(lim);
for(int i=1;i<=cnt;++i)
for(int j=lim/pri[i];j;--j)
tot[j]+=tot[j*pri[i]];
for(int i=1;i<=lim;++i)g[i]=tot[i]*mu[i];
for(int i=1;i<=cnt;++i)
for(int j=1;j*pri[i]<=lim;++j)
g[j*pri[i]]+=g[j];
for(int i=1;i<=lim;++i)S[i]=_2[tot[i]]-1;
for(int i=cnt;i;--i)
for(int j=1;j*pri[i]<=lim;++j)
upd(S[j]-=S[j*pri[i]]);
for(register int i=lim;i>1;--i)
ans=(ans+(LL)S[i]*g[i])%md;
cout<<ans<<'\n';
return 0;
}