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 integerT 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 containsn 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 denotesE · (2n - 1) modulo 998244353.
Sample Input
1
5 1
1 2 3 4 5
Sample Output
42
Author: LIN, Xi
Source: The 15th Zhejiang University Programming Contest
题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?
problemId=5480
题目大意：给一个集合。{xi}为它的一个非空子集。设E为[gcd(x1,x2,…,xm)]k 的期望，求E*(2^n - 1) mod 998244353
题目分析：首先一个有n个元素的集合的非空子集个数为2^n - 1，所以E的分母就是2^n - 1了。因此我们要求的仅仅是E的分子,
设F(x)为gcd(xi) = x的个数，那么ans = (1^k) * F(1) + (2^k) * F(2) + ... + (ma^k) * F(ma)
以下的问题就是怎样高速的计算F(x)了。对于一个集合，先计算出x的倍数的个数，nlogn就可以。然后就是基础的容斥。如果如今要求gcd为1的，那就减去gcd为2的，gcd为3的，注意到6同一时候是2和3的倍数，也就是6的倍数被减了两次，所以要加上gcd为6的，前面的系数刚好是数字相应的莫比乌斯函数，看到这题非常多用dp来容斥的，事实上本质和莫比乌斯函数一样，可是莫比乌斯函数写起来真的非常easy。2333333
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
int const MOD = 998244353;
int const MAX = 1e6 + 5;
ll two[MAX];
int p[MAX], mob[MAX], num[MAX], cnt[MAX];
bool noprime[MAX];
int n, k, ma, pnum;
void Mobius()
{
pnum = 0;
mob[1] = 1;
for(int i = 2; i < MAX; i++)
{
if(!noprime[i])
{
p[pnum ++] = i;
mob[i] = -1;
}
for(int j = 0; j < pnum && i * p[j] < MAX; j++)
{
noprime[i * p[j]] = true;
if(i % p[j] == 0)
{
mob[i * p[j]] = 0;
break;
}
mob[i * p[j]] = -mob[i];
}
}
}
ll qpow(ll x, ll n)
{
ll res = 1;
while(n != 0)
{
if(n & 1)
res = (res * x) % MOD;
x = (x * x) % MOD;
n >>= 1;
}
return res;
}
void pre()
{
Mobius();
two[0] = 1;
for(int i = 1; i < MAX; i++)
two[i] = two[i - 1] * 2ll % MOD;
}
int main()
{
pre();
int T;
scanf("%d", &T);
while(T --)
{
memset(num, 0, sizeof(num));
memset(cnt, 0, sizeof(cnt));
ma = 0;
int tmp;
scanf("%d %d", &n, &k);
for(int i = 0; i < n; i++)
{
scanf("%d", &tmp);
cnt[tmp] ++;
ma = max(ma, tmp);
}
for(int i = 1; i <= ma; i++)
for(int j = i; j <= ma; j += i)
num[i] += cnt[j]; //求i的倍数的个数
ll ans = 0;
for(int i = 1; i <= ma; i++) //枚举gcd
{
ll sum = 0;
for(int j = i; j <= ma; j += i) //容斥
sum = (MOD + sum % MOD + mob[j / i] * (two[num[j]] - 1) % MOD) % MOD;
ans = (MOD + ans % MOD + (sum * qpow(i, k)) % MOD) % MOD;
}
printf("%lld
", ans);
}
}