#ABC162C. Sum of gcd of Tuples (Easy)

Sum of gcd of Tuples (Easy)

题目描述

Find $\displaystyle{\sum_{a=1}^{K}\sum_{b=1}^{K}\sum_{c=1}^{K} \gcd(a,b,c)}$.

Here gcd(a,b,c)\gcd(a,b,c) denotes the greatest common divisor of aa, bb, and cc.

查找 $\displaystyle{\sum_{a=1}^{K}\sum_{b=1}^{K}\sum_{c=1}^{K} \gcd(a,b,c)}$ 。

这里的 gcd(a,b,c)\gcd(a,b,c) 表示 aabbcc 的最大公约数。

输入格式

输入内容按以下格式标准输入:

KK

输出格式

打印 $\displaystyle{\sum_{a=1}^{K}\sum_{b=1}^{K}\sum_{c=1}^{K} \gcd(a,b,c)}$ 的值。

样例 #1

样例输入 #1

2

样例输出 #1

9

样例 #2

样例输入 #2

200

样例输出 #2

10813692

说明

数据规模与约定

  • 1K2001 \leq K \leq 200
  • KK 是整数。

样例 11 解释

gcd(1,1,1)+gcd(1,1,2)+gcd(1,2,1)+gcd(1,2,2)\gcd(1,1,1)+\gcd(1,1,2)+\gcd(1,2,1)+\gcd(1,2,2) +gcd(2,1,1)+gcd(2,1,2)+gcd(2,2,1)+gcd(2,2,2)+\gcd(2,1,1)+\gcd(2,1,2)+\gcd(2,2,1)+\gcd(2,2,2) =1+1+1+1+1+1+1+2=9=1+1+1+1+1+1+1+2=9

因此,答案为 99