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}.
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.
For each case, if the expectation is E, output a single integer denotes E · (2n - 1) modulo 998244353.
1 5 1 1 2 3 4 5
42
對於N個數的序列，所有非空子集中，其期望是GCD的k次方
輸出期望乘以（2^N-1）的值
題目中1的概率是26/31，2的概率是2/32,3,4,5的概率是1/32
期望則是42/32,所以答案為42，也就是說我們的目標是求出期望的分子部分即可
對於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同理；
#include#include #include #include #include #include
