#347. 最大公约数

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Grapes

题目描述

定义:整数 a 和整数 b 的共有约数中最大的一个叫做 a b 的最大公约数,记做 \gcd(a,b)
嗯,你已经学会了什么是最大公约数,我们来做一道简单的练习题吧!
ex0.1: 求当 i<j \sum\limits_{i=1}^n\sum\limits_{j=1}^n\gcd(i,j) 的值 。

输入格式

输入包含多组数据,每组数据含有一个整数 n ,数据间以空格分隔。

输出格式

对于每组数据,输出一行一个整数表示答案。

样例

输入样例

10 100

输出样例

67
13015

数据范围与提示

对于 30\% 的数据,满足 1\leq n\leq 100
对于 60\% 的数据,满足 1\leq n\leq 10000
对于 100\% 的数据,满足 1\leq n\leq 1000000 ,数据组数 \leq 100