给一个集合，大小为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 ;
1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <cmath> 5 #include <iostream> 6 #include <map> 7 #include <list> 8 #include <queue> 9 #include <stack> 10 #include <string> 11 #include <algorithm> 12 #include <iterator> 13 using namespace std; 14 #define MAXN 1000010 15 #define INF 0x3f3f3f3f 16 #define MOD 998244353 17 #define eps 1e-6 18 #define LL long long 19 int num[MAXN]; 20 LL dp[MAXN]; 21 //dp[i] = 2^x -1 ; gcd = n*i; 22 //for(int j = i ; j <= max_num ; j += i) dp[i] -= dp[j]; 23 LL qpow(LL x , LL k) 24 { 25 LL res=1; 26 while(k) 27 { 28 if(k & 1) res = res * x % MOD; 29 x = x * x % MOD; 30 k >>= 1; 31 } 32 return res; 33 } 34 35 int main() 36 { 37 int T; 38 int n,k; 39 LL ans; 40 scanf("%d",&T); 41 while(T--) 42 { 43 scanf("%d %d",&n,&k); 44 int x; 45 int max_num = 0; 46 int cunt = 0; 47 memset(num , 0 , sizeof(num)); 48 memset(dp , 0 , sizeof(dp)); 49 for(int i = 0 ; i < n ; i ++) 50 { 51 scanf("%d",&x); 52 num[x] ++; 53 max_num = max(x , max_num); 54 } 55 56 ans = 0; 57 for(int i = max_num ; i >= 1 ; i --) 58 { 59 cunt = 0; 60 dp[i] = 0; 61 for(int j = i ; j <= max_num ; j += i) 62 { 63 cunt += num[j]; 64 if(j > i) dp[i] = (dp[i] - dp[j] + MOD) % MOD; 65 } 66 dp[i] = (dp[i] + qpow(2 , cunt) - 1 + MOD) % MOD; 67 ans = (ans + (dp[i] * qpow(i , k)) % MOD ) % MOD; 68 } 69 printf("%d\n",(int)ans); 70 } 71 return 0; 72 }