P15367 Autumn Limited Maximum Spanning Tree Problem.


**This problem guarantees that the testdata is generated randomly.** There is a complete graph with $n$ vertices, numbered $1,2,\ldots,n$. Between vertices $i$ and $j$, there is an undirected edge with weight $\mathrm{lcm}(i,j)+\mathrm{gcd}(i,j)$. Please find the total weight of the maximum spanning tree of this graph, modulo $2^{32}$.

This problem contains multiple test cases. The first line contains an integer $T$, representing the number of test cases. The next $T$ lines each contain one integer $n$, representing the number of vertices.

Output $T$ lines. Each line contains one integer, representing the answer for one test case.

**There are subtasks.** ## Constraints - For $5\%$ of the testdata, $T=1,n\leq 2000$. - For $15\%$ of the testdata, $T=1,n\leq 10^6$. - For $30\%$ of the testdata, $T=1,n\leq 10^8$. - For $50\%$ of the testdata, $T=1,n\leq 10^{10}$. - For $75\%$ of the testdata, $T=1,n\leq 10^{15}$. - For $100\%$ of the testdata, $T\leq 10,n\leq 10^{18}$. A fast Pollard_Rho prime factorization code is provided in the distributed files. Translated by ChatGPT 5