Portal
Portal: Luogu
Description
众所周知，czmppppp是数学大神犇。一天，他给众蒟蒻们出了一道数论题，蒟蒻们都惊呆了。。。
给定正整数$N$，求LCM(1, N) + LCM(2, N) + ... + LCM(N, N)。
Input
第一行一个数$T$，表示有$T$组数据。
对于每组数据，一行，一个正整数$N$。
Output
$T$行，每行为对应答案。
Sample Input
3
1
2
5Sample Output
1
4
55Hint
对于$30\%$的数据，$1 \le T \le 5$，$1 \le N \le 100000$；
对于$100\%$的数据，$1 \le T \le 300000$，$1 \le N \le 1000000$。
Solution
题目中的式子可以化简为：
$$\begin{aligned} \sum^{n}_{i = 1}{\text{lcm}(i, n)} & = \sum^{n}_{i = 1}{\frac{i \times n}{\gcd(i, n)}} \\ & = n \times \sum^{n}_{i = 1}{\frac{i}{\gcd(i, n)}} \\ & = n \times \sum_{d | n}\sum_{i = 1}^{n}\frac{i}{d} \times (d == \gcd(i, n)) \\ & = \frac{n}{d} \times \sum_{d | n}\sum^{n}_{i = 1}d == \gcd(i, n) \end{aligned} \\\ \text{当}\gcd(i, n) == 1 \text{时，} \gcd(n - i, n) == 1 (i, n - i \ne 1) \\ \therefore \frac{n}{d} \times \sum_{d | n}\sum^{n}_{i = 1}d == \gcd(i, n) \\ = \sum_{i = 1}^{n}i \times (\gcd(i, n) == 1)= n \times \frac{\varphi(d)}{2}$$
Code
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long LL;
const int MAXN = 1000005;
int T;
LL n, cnt, ans[MAXN], phi[MAXN], prime[MAXN];
inline void calc_phi() {//计算phi函数
phi[1] = 1;
for (int i = 2; i <= MAXN; i++) {
if (!phi[i]) {
prime[++cnt] = i;
phi[i] = i - 1;
}
for (int j = 1; j <= cnt; j++) {
if (i * prime[j] >= MAXN) break;
if (i % prime[j] == 0) {
phi[i * prime[j]] = phi[i] * prime[j];
break;
} else phi[i * prime[j]] = phi[i] * (prime[j] - 1);
}
}
}
int main() {
scanf("%d", &T);
calc_phi();
for (int i = 1; i <= MAXN; i++)
for (int j = i; j <= MAXN; j += i)
ans[j] += phi[(j / i)] * (j / i) + 1 >> 1;//最后推出的式子
while (T--) {
scanf("%lld", &n);
printf("%lld\n", n * ans[n]);//最后主题要×n
}
return 0;
}Article Author: XiaoHuang