题解
(2900) 就这？
可以发现要求的无非是：
[egin{aligned}
2sum_{Asubset S} [gcd{A}=1]lvert A
vert-nsum_{Asubset S} [gcd{A}=1]
end{aligned}
]
考虑一个常见套路：对于数集 (A)，限定 (Bsubset Aland gcd{B}=k) 是不好做的，但 (kmidgcd{B}) 是好做的：其充要条件就是 (forall xin B,kmid x)。于是对于每个 (k)，先统计出来这样的答案 (f_k)，然后倒序枚举 (k)，令 (f_kgets f_k-sum_{kmid i} f_i) 即可。这个可以用狄利克雷前缀和做到 (mathcal{O}(Vloglog V))。
然后就做完了，整体复杂度是 (mathcal{O}(n+Vloglog V))，代码写的是 (mathcal{O}(n+Vlog V)) 做法，懒得改了。
代码
#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
#define For(Ti,Ta,Tb) for(int Ti=(Ta);Ti<=(Tb);++Ti)
#define Dec(Ti,Ta,Tb) for(int Ti=(Ta);Ti>=(Tb);--Ti)
template<typename T> void Read(T &_x){
_x=0;int _f=1;
char ch=getchar();
while(!isdigit(ch)) _f=(ch=='-'?-1:_f),ch=getchar();
while(isdigit(ch)) _x=_x*10+(ch^48),ch=getchar();
_x*=_f;
}
template<typename T,typename... Args> void Read(T &_x,Args& ...others){
Read(_x);Read(others...);
}
typedef long long ll;
const int N=5e5+5,V=1e7+5,Mod=1e9+7;
int n,a[N];
int prime[V/10],prCnt=0;
bool vis[V];
void Sieve(int mx){
vis[1]=1;
For(i,2,mx){
if(!vis[i]) prime[++prCnt]=i;
for(int j=1;j<=prCnt&&i*prime[j]<=mx;++j){
vis[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
}
void Dirichlet(int mx,ll *arr,int inv){
For(i,1,prCnt){
for(int j=1;prime[i]*j<=mx;++j){
arr[j]=(arr[j]+Mod+1LL*inv*arr[prime[i]*j])%Mod;
}
}
}
int cnt[V];
ll pow2[N],f[V],g[V];
int main(){
Read(n);
pow2[0]=1;
For(i,1,n) pow2[i]=pow2[i-1]*2%Mod;
int mx=0;
For(i,1,n) Read(a[i]),mx=max(mx,a[i]),++cnt[a[i]];
Sieve(mx);
For(i,1,mx){
int cur=0;
for(int j=1;j*i<=mx;++j) cur+=cnt[i*j];
if(cur) f[i]=cur*pow2[cur-1]%Mod,g[i]=(pow2[cur]-1+Mod)%Mod;
}
Dirichlet(mx,f,-1);
Dirichlet(mx,g,-1);
ll ans=f[1]*2%Mod-g[1]*n%Mod;
printf("%lld
",(ans+Mod)%Mod);
return 0;
}