A1886. 疯狂 LCM
编程题
提高+/省选-
知识点
题目描述
众所周知，czmppppp 是数学大神犇。一天，他给众蒟蒻们出了一道数论题，蒟蒻们都惊呆了。给定 $n$，求
$$\sum_{i = 1}^n \operatorname{lcm}(i, n)$$
其中 $\operatorname{lcm}(i, j)$ 表示 $i$ 和 $j$ 的最小公倍数。
$$\sum_{i = 1}^n \operatorname{lcm}(i, n)$$
其中 $\operatorname{lcm}(i, j)$ 表示 $i$ 和 $j$ 的最小公倍数。
输入格式
**本题单测试点内有多组数据**。
输入的第一行是一个整数 $T$，表示数据组数。
接下来 $T$ 行，每行一个整数，表示一组数据的 $n$。
输入的第一行是一个整数 $T$，表示数据组数。
接下来 $T$ 行，每行一个整数，表示一组数据的 $n$。
输出格式
对于每组数据，输出一行一个整数表示答案。
输入输出样例
输入 #1
3 1 2 5
输出 #1
1 4 55
说明/提示
#### 数据规模与约定
- 对于 $30\%$ 的数据，保证 $T \leq 5$，$n \leq 10^5$。
- 对于 $100\%$ 的数据，$1 \leq T \leq 3 \times 10^5$，$1 \leq n \leq 10^6$。
- 对于 $30\%$ 的数据，保证 $T \leq 5$，$n \leq 10^5$。
- 对于 $100\%$ 的数据，$1 \leq T \leq 3 \times 10^5$，$1 \leq n \leq 10^6$。