题意重述

我们需要计算：

$$S(n) = \sum_{i=1}^n \mathrm{lcm}(i, n).$$

其中 $1 \le n \le 10^6$，询问次数 $T \le 3\times 10^5$。

---

第一步：公式推导

已知 $\mathrm{lcm}(i, n) = \frac{i \cdot n}{\gcd(i, n)}$。

所以：

$$S(n) = \sum_{i=1}^n \frac{i \cdot n}{\gcd(i, n)} = n \sum_{i=1}^n \frac{i}{\gcd(i, n)}. $$

---

第二步：按 $\gcd$ 分组

设 $d = \gcd(i, n)$，则 $i = d \cdot k$，其中 $\gcd(k, n/d) = 1$，且 $1 \le k \le n/d$。

于是：

$$\frac{i}{\gcd(i, n)} = \frac{d \cdot k}{d} = k.$$

因此：

$$S(n) = n \sum_{d \mid n} \sum_{\substack{1 \le k \le n/d \\ \gcd(k, n/d) = 1}} k. $$

这里 $d$ 取遍 $n$ 的所有正因数。

---

第三步：简化内层求和

设 $m = n/d$，则内层求和为：

$$\sum_{\substack{1 \le k \le m \\ \gcd(k, m) = 1}} k. $$

这是一个经典结论：小于等于 $m$ 且与 $m$ 互质的数的和等于 $\frac{m \cdot \varphi(m)}{2}$，当 $m \ge 2$ 时成立；当 $m=1$ 时，和为 $1$，公式同样适用（因为 $\varphi(1)=1$，$\frac{1\times 1}{2} = 0.5$，但整数求和是 $1$，所以需要单独处理）。

更精确地：

$$\sum_{\substack{1 \le k \le m \\ \gcd(k, m) = 1}} k = \begin{cases} 1 & m = 1, \\ \frac{m \cdot \varphi(m)}{2} & m \ge 2. \end{cases} $$

对于 $m \ge 2$，互质的数成对出现（$k$ 与 $m-k$ 互质且和为 $m$），所以总共有 $\varphi(m)/2$ 对，每对和 $m$，总和 $\frac{m \cdot \varphi(m)}{2}$。

---

第四步：代回原式

于是：

$$S(n) = n \sum_{d \mid n} f\left(\frac{n}{d}\right), $$

其中

$$f(m) = \begin{cases} 1 & m = 1, \\ \frac{m \cdot \varphi(m)}{2} & m \ge 2. \end{cases} $$

我们可以写成：

$$S(n) = n \sum_{d \mid n} f(d).$$

因为 $d$ 和 $n/d$ 都是 $n$ 的因数，求和是对称的。

所以：

$$S(n) = n \left[ f(1) + \sum_{\substack{d \mid n \\ d \ge 2}} \frac{d \cdot \varphi(d)}{2} \right]. $$

其中 $f(1) = 1$。

因此：

$$S(n) = n \left( 1 + \frac{1}{2} \sum_{\substack{d \mid n \\ d \ge 2}} d \cdot \varphi(d) \right). $$

令

$$g(n) = \sum_{d \mid n} d \cdot \varphi(d).$$

则

$$S(n) = n \cdot \frac{g(n) + 1}{2}.$$

注意：当 $d=1$ 时，$d \cdot \varphi(d) = 1$，所以 $g(n) = 1 + \sum_{d \mid n, d \ge 2} d \cdot \varphi(d)$。
因此 $S(n) = n \cdot \frac{g(n) + 1}{2}$ 等价于上面的公式。

---

第五步：计算 $g(n)$

我们要求：

$$g(n) = \sum_{d \mid n} d \cdot \varphi(d).$$

这是一个积性函数，因为 $d \cdot \varphi(d)$ 是积性函数，且因子求和保持积性。

---

证明 $h(d) = d \cdot \varphi(d)$ 是积性函数

• $\varphi$ 是积性函数。
• $d$ 显然是积性函数。
• 两个积性函数的乘积是积性函数。

所以 $h(d)$ 是积性函数。
那么 $g(n) = \sum_{d|n} h(d)$ 是 $h$ 的狄利克雷卷积 $h * 1$，两个积性函数的卷积也是积性函数。
因此 $g(n)$ 是积性函数。

---

第六步：求 $g(n)$ 的表达式

因为 $g(n)$ 积性，只需计算 $g(p^k)$，其中 $p$ 是素数。

$$g(p^k) = \sum_{d \mid p^k} d \cdot \varphi(d).$$

$p^k$ 的因数有 $1, p, p^2, \dots, p^k$。

所以：

$$g(p^k) = \sum_{j=0}^k p^j \cdot \varphi(p^j).$$

已知 $\varphi(p^j) = p^j - p^{j-1}$（当 $j \ge 1$），$\varphi(1)=1$。

所以：

• $j=0$：$p^0 \cdot \varphi(1) = 1 \cdot 1 = 1$。
• $j \ge 1$：$p^j \cdot (p^j - p^{j-1}) = p^{2j} - p^{2j-1}$。

因此：

$$g(p^k) = 1 + \sum_{j=1}^k (p^{2j} - p^{2j-1}).$$

这是一个几何级数：

$$\sum_{j=1}^k p^{2j} = \frac{p^{2(k+1)} - p^2}{p^2 - 1}, $$$$\sum_{j=1}^k p^{2j-1} = p \cdot \frac{p^{2k} - 1}{p^2 - 1}. $$

所以：

$$g(p^k) = 1 + \frac{p^{2(k+1)} - p^2}{p^2 - 1} - p \cdot \frac{p^{2k} - 1}{p^2 - 1}. $$

化简： 先通分 $p^2 - 1$：

$$g(p^k) = \frac{(p^2 - 1) + p^{2(k+1)} - p^2 - p^{2k+1} + p}{p^2 - 1}. $$

分子：$p^2 - 1 + p^{2k+2} - p^2 - p^{2k+1} + p = p^{2k+2} - p^{2k+1} + p - 1$。

提取 $p^{2k+1}$：

$$p^{2k+2} - p^{2k+1} = p^{2k+1}(p - 1).$$

所以分子 = $p^{2k+1}(p-1) + (p-1) = (p-1)(p^{2k+1} + 1)$。

因此：

$$g(p^k) = \frac{(p-1)(p^{2k+1} + 1)}{p^2 - 1} = \frac{p^{2k+1} + 1}{p + 1}. $$

最终公式：

$$g(p^k) = \frac{p^{2k+1} + 1}{p + 1}.$$

---

第七步：算法实现步骤

1. 预处理 $1$ 到 $10^6$ 的所有 $\varphi(n)$（欧拉函数）。
2. 利用积性性质计算 $g(n)$：
   • 对每个素数 $p$，计算 $g(p^k)$ 用上述公式。
   • 由于 $g(n)$ 积性，可以用线性筛在 $O(n)$ 内求出所有 $g(n)$。
3. 然后计算：$$S(n) = n \cdot \frac{g(n) + 1}{2}.$$
4. 对于每个询问 $n$，直接输出 $S(n)$。

注意：结果可能很大，要对 $10^9+7$ 取模吗？题目没说取模，但 $n \le 10^6$，$S(n)$ 最大大约在 $10^{18}$ 级别，用 long long 存即可（题目输出整数，应该不用取模）。

---

第八步：复杂度分析

• 预处理 $\varphi$ 和 $g$：$O(n)$。
• 每个询问 $O(1)$。
• 总复杂度 $O(n + T)$，可以应对 $n \le 10^6, T \le 3\times 10^5$。

---

第九步：样例验证

$n=1$

$g(1) = \sum_{d|1} d \varphi(d) = 1 \cdot \varphi(1) = 1$。
$S(1) = 1 \cdot \frac{1+1}{2} = 1$。

$n=2$

因数 $d=1,2$：

• $d=1$：$1\cdot \varphi(1)=1$
• $d=2$：$2\cdot \varphi(2)=2\cdot 1=2$ $g(2)=3$。 $S(2) = 2 \cdot \frac{3+1}{2} = 2 \cdot 2 = 4$。

$n=5$

因数 $d=1,5$：

• $d=1$：1
• $d=5$：$5\cdot \varphi(5)=5\cdot 4=20$ $g(5)=21$。 $S(5) = 5 \cdot \frac{21+1}{2} = 5 \cdot 11 = 55$。

符合样例输出。

---

总结

本题的关键步骤：

1. 将 $\mathrm{lcm}$ 转化为 $\gcd$。
2. 按 $\gcd$ 分组，利用互质数对的求和公式。
3. 引入 $g(n) = \sum_{d|n} d \cdot \varphi(d)$，并证明其积性。
4. 推导 $g(p^k)$ 的封闭形式 $\frac{p^{2k+1}+1}{p+1}$。
5. 用线性筛预处理 $g(n)$，$O(1)$ 回答询问。