P2398 GCD SUM (欧拉函数)

1、首先生成素数序列 prime[i]，随后计算欧拉函数 phi[i]
2、计算 gcd(x, y)，其中 1 <= x <= n，1 <= y <= n，题目的含义等同于存在 n * n 个 gcd(x, y) 的求和问题。若 x < y 且 gcd(x, y) = 1，则小于 y 并与 y 互质的数共有 phi[y] 个。这 phi[y] 组 (x, y) 满足：gcd(k * x, k * y) = k，其中 k 的取值范围为不超过 n / phi[y]。
其对应的 gcd(x, y) 总和 S
= phi[y] * (n / phi[y] + n / phi[y] - 1 + n / phi[y] - 2 + … + 2 + 1)
3、对于从 1 到 n 的每个数，依据上述公式计算出 S，并将所有 S 累加得到 sum(S)。由于 gcd(x, y) = gcd(y, x)，因此最终结果需乘以2，即 sum(S) * 2
4、当两个数相等时，所有 gcd(x, x) 的总和为 (1 + n) * n / 2。
最终得出的结果为：sum(S) * 2 + (1 + n) * n / 2。在处理该问题时应特别注意整数溢出的情况

    #include <cstdio>
    #include <cstring>
    #include <