// // main.cpp // E // // Created by 黄宇凡 on 16/3/18. // Copyright © 2016年 黄宇凡. All rights reserved. // /* #include #include #include #include #include using namespace std; typedef long long ll; const ll mod=1e9+7; const ll maxn=1e6+5; ll mod_pow(ll x,ll n){ ll res=1; while(n>0){ if(n&1) res=res*x%mod; x=x*x%mod; n>>=1; } return res; } ll n,k; ll a[maxn]; ll cnt[maxn]; ll power[maxn]; ll ans[maxn]; int main(int argc, const char * argv[]) { int T; cin>>T; while(T--){ scanf("%lld",&n); ll maxa=0; memset(cnt,0,sizeof(cnt)); for(int i=1;i<=n;i++){ scanf("%lld",a+i); maxa=max(maxa,a[i]); cnt[a[i]]++; } power[0]=1; for(int i=1;i<=n;i++){ power[i]=(power[i-1]*2)%mod; } ans[1]=1; for(int i=2;i<=maxa;i++){ ans[i]=mod_pow(i,k); } for(int i=1;i<=maxa;i++){ for(int j=i+i;j<=maxa;j+=i){ ans[j]=(ans[j]-ans[i])%mod; } } ll exp=0; for(int i=1;i<=maxa;i++){ ll count=cnt[i]; for(int j=i+i;j<=maxa;j+=i){ count+=cnt[j]; } exp+=(power[count]-1)*ans[i]%mod; exp%=mod; } cout<<(exp+mod)%mod< #include #include #include #include using namespace std; typedef long long ll; const ll mod= 100000007; const ll maxn=1e6+5; ll mod_pow(ll x,ll n){ ll res=1; while(n>0){ if(n&1) res=res*x%mod; x=x*x%mod; n>>=1; } return res; } ll n,k; ll a[maxn]; ll cnt[maxn]; ll power[maxn]; ll ans[maxn]; int main(int argc, const char * argv[]) { int T; cin>>T; while(T--){ scanf("%lld",&n); k=1; ll maxa=0; memset(cnt,0,sizeof(cnt)); for(int i=1;i<=n;i++){ scanf("%lld",a+i); maxa=max(maxa,a[i]); cnt[a[i]]++; } power[0]=1; for(int i=1;i<=n;i++){ power[i]=(power[i-1]*2)%mod; } ans[1]=1; for(int i=2;i<=maxa;i++){ ans[i]=mod_pow(i,k); } for(int i=1;i<=maxa;i++){ for(int j=i+i;j<=maxa;j+=i){ ans[j]=(ans[j]-ans[i])%mod; } } ll exp=0; for(int i=1;i<=maxa;i++){ ll count=cnt[i]; for(int j=i+i;j<=maxa;j+=i){ count+=cnt[j]; } exp+=(power[count]-1)*ans[i]%mod; exp%=mod; } cout<<(exp+mod)%mod<