Chef and Sums SOLUTIONS CHEFSUMS

Chef and Sums SOLUTION

Gourmet specialist gave you a grouping of whole numbers a1,a2,… ,aN and 3 whole numbers K, m and x. We should characterize the accompanying capacities: 
 
G(i1,… ,iK)=gcd(ai1,… ,aiK) 
 
Sx(i1,… ,iK)=axi1+axi2+… +axiK 
 
Pm(i1,… ,iK)=(ai1⋅ai2⋅… ⋅aiK)m 
 
W(T)=smallestprimedivisorofP1(T) 
 
Culinary expert needs you to figure the whole of G(T)⋅W(T)⋅Sx(T)⋅Pm(T) over all K-tuples of records T=(i1,i2,… ,iK) with the end goal that ij∈{1,2,… ,N} for each legitimate j (there are NK of these K-tuples). Since this whole could be tremendous, register it modulo 109+7. 
 
Information 
 
The principal line of the info contains four space-isolated whole numbers N, K, m and x. 
 
The subsequent line contains N space-isolated numbers a1,a2,… ,aN. 
 
Yield 
 
Print a solitary line containing one whole number ∑TG(T)⋅W(T)⋅Sx(T)⋅Pm(T) modulo 109+7. 
 
Requirements 
 
1≤N≤106 
 
1≤K,m,x≤1018 
 
2≤ai≤106 for each legitimate I 
 
Subtasks 
 
Subtask #1 (5 focuses): 
 
N≤10 
 
K≤6 
 
Subtask #2 (20 focuses): for each legitimate I, ai is even 
 
Subtask #3 (75 focuses): unique requirements 
 
Model Input 
 
3 2 1 
 
2 3 4 
 
Model Output 
 
2414 
 
Clarification 
 
Model case 1: We have NK=32=9 potential sets T of records. The comparing summands are: 
 
T=(1,1): gcd(2,2)⋅(21+21)⋅(2⋅2)1⋅2=64 
 
T=(1,2): gcd(2,3)⋅(21+31)⋅(2⋅3)1⋅2=60 
 
T=(1,3): gcd(2,4)⋅(21+41)⋅(2⋅4)1⋅2=192 
 
T=(2,1): gcd(3,2)⋅(31+21)⋅(3⋅2)1⋅2=60 
 
T=(2,2): gcd(3,3)⋅(31+31)⋅(3⋅3)1⋅3=486 
 
T=(2,3): gcd(3,4)⋅(31+41)⋅(3⋅4)1⋅2=168 
 
T=(3,1): gcd(4,2)⋅(41+21)⋅(4⋅2)1⋅2=192 
 
T=(3,2): gcd(4,3)⋅(41+31)⋅(4⋅3)1⋅2=168 
 
T=(3,3): gcd(4,4)⋅(41+41)⋅(4⋅4)1⋅2=1024 
 
Their aggregate modulo 109+7 is 2414.

Leave a Comment

close
error: Content is protected !!