/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 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)} の値を出力せよ。
入力例 1
2
出力例 1
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 です。
入力例 2
200
出力例 2
10813692
Score : 300 points
Problem Statement
Find \displaystyle{\sum_{a=1}^{K}\sum_{b=1}^{K}\sum_{c=1}^{K} \gcd(a,b,c)}.
Here \gcd(a,b,c) denotes the greatest common divisor of a, b, and c.
Constraints
- 1 \leq K \leq 200
- K is an integer.
Input
Input is given from Standard Input in the following format:
K
Output
Print the value of \displaystyle{\sum_{a=1}^{K}\sum_{b=1}^{K}\sum_{c=1}^{K} \gcd(a,b,c)}.
Sample Input 1
2
Sample Output 1
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
Thus, the answer is 9.
Sample Input 2
200
Sample Output 2
10813692