Zoj 3868 GCD Expectation

 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 }