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).
