配点 : $300$ 点

問題文

$\displaystyle{\sum_{a=1}^{K}\sum_{b=1}^{K}\sum_{c=1}^{K} \gcd(a,b,c)}$ を求めてください。

ただし、$\gcd(a,b,c)$ は $a,b,c$ の最大公約数を表します。

制約

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

入力

入力は以下の形式で標準入力から与えられる。

$K$

出力

$\displaystyle{\sum_{a=1}^{K}\sum_{b=1}^{K}\sum_{c=1}^{K} \gcd(a,b,c)}$ の値を出力せよ。

2

9

$\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$ です。

200

10813692