Rating:
This is PPC problem.
For any `i, v, x`, we define `cnt(i,v,x)` as the number of `P` such that `GCD(P)=v` and `P[i]=x`.
Then, the answer will be `\sum_{i,v,x} cnt(i,v,x) * v * c[x] * i`.
Because `cnt(i,v,x) = cnt(i',v,x)`, the answer can be written as `\sum_{v,x} cnt(0,v,x) * v * c[x] * N*(N-1)/2`.
To count `cnt(0,v,x)`, we fix `x`. Then we check `v` from `N-1` to `1` such that `x % v = 0`.
Because `GCD(P)=v`, all elements of `P` are multiple of `v` (including 0).
The total number of `P` with multiples of `v` is `((N-1)//v + 1)^{N-1}`.
However, this contains some `P` with `GCD(P)=2v, 3v, ...`, so we subtract them from earlier calculations.
This algorithm looks working with `O(N^2 log N)` time complexity (`log N` is come from harmonic series of subtraction phase).
