最大公约数之和(GCD SUM)

求

$\sum_{i=1}^n \sum_{j=1}^n \gcd(i, j)$

第一行一个整数 $n$ 。

第一行一个整数表示答案。

对于 $30\%$ 的数据， $n\leq 3000$ 。

对于 $60\%$ 的数据， $7000\leq n\leq 7100$ 。

对于 $100\%$ 的数据， $n\leq 10^5$ 。

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1600。

Subtask	分值	测试点编号	说明
0	10	1	样例
1	25	2~8	小规模 n≤3000 / 特殊: n=1
2	25	9~15	中等规模 7000≤n≤7100
3	20	16~20	大规模 n≤50000
4	20	21~25	满规模 n≤100000 欧拉函数前缀和测试

出处：原题链接

#P2398. 最大公约数之和(GCD SUM)