AT_abc162_c [ABC162C] Sum of gcd of Tuples (Easy)

题目描述

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

其中，$\gcd(a,b,c)$ 表示 $a,b,c$ 的最大公约数。

输入格式

输入为以下格式，从标准输入读取。

$K$

输出格式

请输出 $\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

说明/提示

限制条件

• $1 \leq K \leq 200$
• $K$ 是整数

样例解释 1

$\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)$ $=1+1+1+1+1+1+1+2=9$，因此答案为 $9$。

由 ChatGPT 4.1 翻译