There exists a solution with time complexity \(O(nD+n\ln n)\).

First, we do prime factorization for all \(a_i\). And for each factor \(j\) of \(a_i\), put node \(i\) to a set of points \(V_j\). Let \(G_j\) be the induced subgraph of \(V_j\) in the original grah \(G\). It’s easy to see for each \(j\), \(G_j\) is a forest. We traverse each tree in \(G_j\), and get \(f_j=\) the sum of \(dis(x,y)\) (the distance between node \(x\) and \(y\)). This can be simply done by “changing the root of tree” trick.

Then we can use inclusion-exclusion to calculate \(f'_i=f_i-\sum\limits_{i|j,i<j} f'_{j}\)(we calculate \(f'_i\) from \(\max a\) to \(1\)). The answer is \(\sum i\cdot f'_i\).

Sample Code(C++)