Random Chocolates

All submissions for this problem are available.
### Read problems statements in [Hindi](http://www.codechef.com/download/translated/COOK116/hindi/RANDCHCL.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/COOK116/mandarin/RANDCHCL.pdf), [Russian](http://www.codechef.com/download/translated/COOK116/russian/RANDCHCL.pdf), [Vietnamese](http://www.codechef.com/download/translated/COOK116/vietnamese/RANDCHCL.pdf), and [Bengali](http://www.codechef.com/download/translated/COOK116/bengali/RANDCHCL.pdf) as well. We all know that Chef got a box of $N$ chocolates (numbered $1$ through $N$) as his birthday present. For each valid $i$, the $i$th chocolate has a sweetness value $W_i$. Chef is going to play the following randomised game for fun with his brother:  First, an integer $k$ between $1$ and $N$ (inclusive) is chosen uniformly randomly.  Then, $k$ times, Chef chooses a chocolate from the box uniformly randomly and independently (each chocolate may be chosen multiple times). For each $i$ ($1 \le i \le k$), let's denote the sweetness of the $i$th chocolate chosen by Chef by $A_i$.  Chef's brother does the same thing ― $k$ times, he also chooses a chocolate from the box uniformly randomly and independently from each other or Chef's choices (so each chocolate may still be chosen multiple times). For each $i$ ($1 \le i \le k$), let's denote the sweetness of the $i$th chocolate chosen by Chef's brother by $B_i$.  The score of the game is $\sum_{i=1}^k \sum_{j=1}^k \mathrm{gcd}(A_i, B_j)$. Find the expected value of the score. It can be proved that this expected value can be expressed as a fraction $\frac{P}{Q}$, where $P$ and $Q$ are positive integers and $Q$ is coprime with $998,244,353$. You should compute $P \cdot Q^{1}$ modulo $998,244,353$, where $Q^{1}$ denotes the multiplicative inverse of $Q$ modulo $998,244,353$. ### Input  The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.  The first line of each test case contains a single integer $N$.  The second line contains $N$ spaceseparated integers $W_1, W_2, \ldots, W_N$. ### Output For each test case, print a single line containing one integer $P \cdot Q^{1}$ modulo $998,244,353$. ### Constraints  $1 \le T \le 5$  $1 \le N \le 3 \cdot 10^5$  $1 \le W_i \le 5 \cdot 10^5$ for each valid $i$ ### Example Input ``` 2 3 1 2 3 4 2 2 2 2 ``` ### Example Output ``` 887328320 15 ``` ### Explanation **Example case 2:**  When $k = 1$, the score is $1^2 \cdot 2 = 2$.  When $k = 2$, the score is $2^2 \cdot 2 = 8$.  When $k = 3$, the score is $3^2 \cdot 2 = 18$.  When $k = 4$, the score is $4^2 \cdot 2 = 32$. The expected score is $\frac{2+8+18+32}{4} = 15$.Author:  imanik 
Editorial  https://discuss.codechef.com/problems/RANDCHCL 
Tags  combinatorics, cook116, imanik, medium, tmwilliamlin 
Date Added:  14032020 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, CPP17, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 