给一个集合，大小为n ， 求所有子集的gcd 的期望和 。
期望的定义为 这个子集的最大公约数的K次方 ；
每个元素被选中的概率是等可能的
即概率 p = (发生的事件数)/(总的事件数);
总的事件数 = 2^n -1; 大小为n的集合的非空子集个数为2^n -1
期望 = p(i) *i;
= 1*p(1) + 2*p(2) + ... +n*p(n);
设x发生的事件数为 dp[x] ， 则上式可化简为：
=1*dp[1]/(2^n-1) + 2*dp[2]/(2^n-1) + ... +n*dp[n]/(2^n-1);
=1/(2^n-1)*(1*dp[1] + 2*dp[2] + ... + n*dp[n]);
题目要求最后所得结果乘以 (2^n-1);
所以式子最后化简为：1*dp[1] + 2*dp[2] + ... + n*dp[n]
即问题转化为求gcd = i 的子集数
假设gcd = m*i (m = 0,1,2,3,... && m*i <= max_num)的个数为dp[i]个
那么gcd = i 的个数则为 for(int j= i + i ; j <= max_num ; j += i) dp[i]-=dp[j] ;
则期望为：dp[1] * 1^k + dp[2] * 2^k + ... dp[i] * i^k ;
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
#include <iterator>
using namespace std;
#define MAXN 1000010
#define INF 0x3f3f3f3f
#define MOD 998244353
#define eps 1e-6
#define LL long long
int num[MAXN];
LL dp[MAXN];
//dp[i] = 2^x -1 ; gcd = n*i;
//for(int j = i ; j <= max_num ; j += i) dp[i] -= dp[j];
LL qpow(LL x , LL k)
{
LL res=;
while(k)
{
if(k & ) res = res * x % MOD;
x = x * x % MOD;
k >>= ;
}
return res;
} int main()
{
int T;
int n,k;
LL ans;
scanf("%d",&T);
while(T--)
{
scanf("%d %d",&n,&k);
int x;
int max_num = ;
int cunt = ;
memset(num , , sizeof(num));
memset(dp , , sizeof(dp));
for(int i = ; i < n ; i ++)
{
scanf("%d",&x);
num[x] ++;
max_num = max(x , max_num);
} ans = ;
for(int i = max_num ; i >= ; i --)
{
cunt = ;
dp[i] = ;
for(int j = i ; j <= max_num ; j += i)
{
cunt += num[j];
if(j > i) dp[i] = (dp[i] - dp[j] + MOD) % MOD;
}
dp[i] = (dp[i] + qpow( , cunt) - + MOD) % MOD;
ans = (ans + (dp[i] * qpow(i , k)) % MOD ) % MOD;
}
printf("%d\n",(int)ans);
}
return ;
}