记一个集合的gcd为该集合内所有数的最大公约数，
求一个给定集合的非空子集的gcd的k次方的期望~
Input
第一行有一个数t,表示数据组数
接下去每组数据两行，第一行两个数n,k(0 <n,k<=10^6),表示该集合有n个数字。 <br="">第二行有n个数ai(0<=ai<=2000000)代表该集合内的所有元素。
Output
每组数据输出一行，为期望乘上2^n-1,之后取模10000007的结果。
Sample Input
2
5 1
1 2 3 4 5
3 2
2 3 6
Sample Output
42
64
Hint
样例2中gcd为1的非空子集集有{2,3},{2,3,6}两个，
2的有{2},{2,6}两个，3的有{3},{3,6}两个，6的有{6}一个。
所以期望是(2*1^2+2*22+2*3^2+1*42)/7=64/7。
题解
这题主要是得求出对应gcd值下的子集个数。对于gcd值，我们能够指定一个值x，那么x的倍数都可以组成任意子集。所以第一步统计每个数字的个数，然后假设当前gcd=x，那么此时的集合内元素数应该为x的倍数的个数。可为了求出所有的值，这里存在重复的，所以我们需要减去一部分，如果从大往小执行，这样减去的就是重复的部分。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int maxn = 2e6+;
const int mod = ;
int cnt[maxn],res[maxn];
LL num[maxn];
LL qpow(LL a,LL b){
LL res=;
while(b){
if(b&) res = (res*a)%mod;
a = (a*a)%mod;
b>>=;
}
return res%mod;
}
int main(){
int t;
scanf("%d",&t);
while(t--){
int n,x,k,maxx=-;
memset(cnt,,sizeof(cnt));
memset(res,,sizeof(res));
memset(num,,sizeof(num));
scanf("%d%d",&n,&k);
for(int i=;i<n;i++){
scanf("%d",&x);
maxx=max(maxx,x);
cnt[x]++;
} for(int i=;i<=maxx;i++){
for(int j=;j*i<=maxx;j++){
res[i] += cnt[i*j];
}
}
for(int i=;i<=maxx;i++)
num[i]=(qpow(,res[i])-+mod)%mod;
for(int i=maxx;i>=;i--){
for(int j=;j*i<=maxx;j++){
num[i] = (num[i]-num[j*i]+mod)%mod;
}
} LL ans = ;
for(int i=;i<=maxx;i++){
ans = (ans+num[i]*qpow(i,k))%mod;
}
cout<<ans<<endl;
}
return ;
}