P15367 秋季限定生成树问题
题目背景
题目描述
**本题保证数据随机生成**
有一个 $n$ 个点的完全图，结点编号为 $1,2……n$，结点 $i,j$ 之间有权值为 $\mathrm{lcm}(i,j)+\mathrm{gcd}(i,j)$ 的无向边。
请你求出这个图的最大生成树的大小，对 $2^{32}$ 取模。
输入格式
本题有多组测试数据，第一行一个整数 $T$ 代表数据组数。
接下来 $T$ 行，每行一个整数 $n$ 代表点数。
输出格式
共 $T$ 行，每行一个整数代表一组数据的答案。
说明/提示
**有子任务限制**
- 对于 $5\%$ 的数据，$T=1,n\leq 2000$。
- 对于 $15\%$ 的数据，$T=1,n\leq 10^6$。
- 对于 $30\%$ 的数据，$T=1,n\leq 10^8$。
- 对于 $50\%$ 的数据，$T=1,n\leq 10^{10}$。
- 对于 $75\%$ 的数据，$T=1,n\leq 10^{15}$。
- 对于 $100\%$ 的数据，$T\leq 10,n\leq 10^{18}$。
下发文件中提供了一份高速的 Pollard_Rho 分解质因数代码。