解题思路

1. 代换：令 $d = \gcd(i,j)$，$i = d \cdot a$，$j = d \cdot b$，则 $\gcd(a,b)=1$ 且 $a < b \le \lfloor n/d \rfloor$，配对权值化为 $a+b$。于是$$\mathrm{Ans}(n) = \sum_{d=1}^{n} f\bigl(\lfloor n/d \rfloor\bigr),$$ 其中 $f(m) = \sum_{1 \le a < b \le m,\; \gcd(a,b)=1} (a+b)$。
2. 莫比乌斯与欧拉函数：用筛法预处理 $[1, 10^6]$ 的最小质因子、欧拉函数 $\varphi$ 与莫比乌斯函数 $\mu$，并预处理模 $10^9+7$ 下的逆元。
3. 线性筛卷积：枚举倍数累加 $\varphi$ 与 $\mu$ 的贡献，得到每个 $m$ 上 $f(m)$ 的相关数组，再对答案数组做前缀和。这样 $\mathrm{Ans}(n)$ 可 $O(1)$ 查询。