#P2398. GCD SUM

    ID: 1406 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>数论数学枚举暴力素数判断质数筛法

GCD SUM

题目描述

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

输入格式

第一行一个整数 nn

输出格式

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

2
5

提示

对于 30%30\% 的数据,n3000n\leq 3000

对于 60%60\% 的数据,7000n71007000\leq n\leq 7100

对于 100%100\% 的数据,n105n\leq 10^5