← 返回题目列表

AtCoder · abc162_c

C. 元组的 gcd 之和(简单)

中文机器翻译题面 查看原题

分数: 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