Edward has a set of n integers {a1, a2,...,an}. He randomly picks a nonempty subset {x1, x2,…,xm} (each nonempty subset has equal probability to be picked), and would like to know the expectation of [gcd(x1, x2,…,xm)]k.
Note that gcd(x1, x2,…,xm) is the greatest common divisor of {x1, x2,…,xm}.
Input
There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:
The first line contains two integers n, k (1 ≤ n, k ≤ 106). The second line contains n integers a1, a2,…,an (1 ≤ ai ≤ 106).
The sum of values max{ai} for all the test cases does not exceed 2000000.
Output
For each case, if the expectation is E, output a single integer denotes E · (2n - 1) modulo 998244353.
Sample Input
1 5 1 1 2 3 4 5
Sample Output
42
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #include <stack> 5 #include <queue> 6 #include<map> 7 #include <set> 8 #include <vector> 9 #include <math.h> 10 using namespace std; 11 #define ls 2*i 12 #define rs 2*i+1 13 #define up(i,x,y) for(i=x;i<=y;i++) 14 #define down(i,x,y) for(i=x;i>=y;i--) 15 #define mem(a,x) memset(a,x,sizeof(a)) 16 #define w(a) while(a) 17 #define LL long long 18 const double pi = acos(-1.0); 19 #define Len 1000005 20 #define mod 998244353 21 const LL inf = 1<<30; 22 LL t,n,k; 23 LL a[Len]; 24 LL two[Len],fun[Len],cnt[Len],vis[Len],maxn; 25 LL power(LL x, LL y) 26 { 27 LL ans = 1; 28 w(y) 29 { 30 if(y&1) ans=(ans*x)%mod; 31 x=(x*x)%mod; 32 y/=2; 33 } 34 return ans; 35 } 36 int main() 37 { 38 LL i,j; 39 scanf("%lld",&t); 40 two[0] = 1; 41 up(i,1,Len-1) two[i] = (two[i-1]*2)%mod; 42 w(t--) 43 { 44 mem(cnt,0); 45 mem(vis,0); 46 scanf("%lld%lld",&n,&k); 47 maxn = 0; 48 up(i,0,n-1) 49 { 50 scanf("%lld",&a[i]); 51 if(!vis[a[i]]) 52 { 53 vis[a[i]] = 1; 54 cnt[a[i]] = 1; 55 } 56 else cnt[a[i]]++; 57 maxn = max(maxn,a[i]); 58 } 59 fun[1] = 1; 60 up(i,2,maxn) fun[i] = power(i,k); 61 up(i,1,maxn) 62 { 63 for(j = i+i; j<=maxn; j+=i) fun[j]=(fun[j]-fun[i])%mod; 64 } 65 LL ans = (two[n]-1)*fun[1]%mod; 66 up(i,2,maxn) 67 { 68 LL cc = 0; 69 for(j = i; j<=maxn; j+=i) 70 { 71 if(vis[j]) cc+=cnt[j]; 72 } 73 LL tem = (two[cc]-1)*fun[i]%mod; 74 ans = (ans+tem)%mod; 75 } 76 printf("%lld ",(ans+mod)%mod); 77 } 78 return 0; 79 }
对于N的序列，肯定有2^N-1个非空子集，其中其最大的GCD不会大于原序列的max，那么我们用数组fun来记录其期望
例如题目中的，期望为1的有26个，期望为2的有2个，期望为3,4,5的都只有1个
我们可以拆分来算，首先对于1，期望为1,1的倍数有5个，那么这五个的全部非空子集为2^5-1种，得到S=(2^5-1)*1;
对于2,2的期望应该是2，但是在期望为1的时候所有的子集中，我们重复计算了2的期望，多以我们应该减去重复计算的期望数，
现在2的期望应该作1算，那么对于2的倍数，有两个，2,4，其组成的非空子集有2^2-1个，所以得到S+=(2^2-1)*1
对于3,4,5同理；