Comments

Here is another way to solve D.

Let us call $$$f_x$$$ mean that is there $$$a_i$$$ is its factor.We can get the values in $$$\Theta(n\ln{n})$$$.

And than we can get the answer:

$$$ \begin{aligned} & \sum\limits_{i=1}^n\sum\limits_{j=1}^n f_{\gcd(a_i,a_j)} \\ & =\sum\limits_{d=1}^n f_d\sum\limits_{i=1}^n\sum\limits_{j=1}^n [\gcd(a_i,a_j)=d] \\ & =\sum\limits_{d=1}^n f_d\sum\limits_{i=1}^n\sum\limits_{j=1}^n [\gcd(\frac{a_i}{d},\frac{a_j}{d})=1][d|a_i][d|a_j]\\ & =\sum\limits_{d=1}^n f_d\sum\limits_{i=1}^n\sum\limits_{j=1}^n \varepsilon(\gcd(\frac{a_i}{d},\frac{a_j}{d}))[d|a_i][d|a_j]\\ & =\sum\limits_{d=1}^n f_d\sum\limits_{i=1}^n\sum\limits_{j=1}^n [d|a_i][d|a_j]\sum\limits_{t|\frac{a_i}{d}\bigwedge t|\frac{a_j}{d}} \mu(t)\\ & =\sum\limits_{d=1}^n f_d\sum\limits_{t=1}^{\lfloor\frac{n}{d}\rfloor} \mu(t)\sum\limits_{i=1}^n\sum\limits_{j=1}^n [dt|a_i][dt|a_j]\\ & =\sum\limits_{d=1}^n f_d\sum\limits_{t=1}^{\lfloor\frac{n}{d}\rfloor} \mu(t)(\sum\limits_{i=1}^n[dt|a_i])^2\\ \end{aligned} $$$

The last $$$\sum$$$ we can solve it in $$$\Theta(n\ln{n})$$$.

So we can solve the problem in $$$\Theta(n\ln{n})$$$.

record link:https://codeforces.me/contest/1884/submission/229180049.