程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> ZOJ3868:GCD Expectation

ZOJ3868:GCD Expectation

編輯:C++入門知識

ZOJ3868:GCD Expectation


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


對於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#include  #include  #include  #include  using namespace std; #define ls 2*i #define rs 2*i+1 #define up(i,x,y) for(i=x;i<=y;i++) #define down(i,x,y) for(i=x;i>=y;i--) #define mem(a,x) memset(a,x,sizeof(a)) #define w(a) while(a) #define LL long long const double pi = acos(-1.0); #define Len 1000005 #define mod 998244353 const LL inf = 1<<30; LL t,n,k; LL a[Len]; LL two[Len],fun[Len],cnt[Len],vis[Len],maxn; LL power(LL x, LL y) { LL ans = 1; w(y) { if(y&1) ans=(ans*x)%mod; x=(x*x)%mod; y/=2; } return ans; } int main() { LL i,j; scanf("%lld",&t); two[0] = 1; up(i,1,Len-1) two[i] = (two[i-1]*2)%mod; w(t--) { mem(cnt,0); mem(vis,0); scanf("%lld%lld",&n,&k); maxn = 0; up(i,0,n-1) { scanf("%lld",&a[i]); if(!vis[a[i]]) { vis[a[i]] = 1; cnt[a[i]] = 1; } else cnt[a[i]]++; maxn = max(maxn,a[i]); } fun[1] = 1; up(i,2,maxn) fun[i] = power(i,k); up(i,1,maxn) { for(j = i+i; j<=maxn; j+=i) fun[j]=(fun[j]-fun[i])%mod; } LL ans = (two[n]-1)*fun[1]%mod; up(i,2,maxn) { LL cc = 0; for(j = i; j<=maxn; j+=i) { if(vis[j]) cc+=cnt[j]; } LL tem = (two[cc]-1)*fun[i]%mod; ans = (ans+tem)%mod; } printf("%lld\n",(ans+mod)%mod); } return 0; } 


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved