GCD Expectation
Time Limit: 4 Seconds Memory Limit: 262144 KB
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
Author: LIN, Xi
Source: The 15th Zhejiang University Programming Contest
Submit Status
題意:給出一個序列,求這個序列子集gcd的k次方和的期望
容斥原理。。。
#include
#include
#include
#include
#include
#include