AtCoder Beginner Contest 162 - 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) 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-----
2

-----Sample Output-----
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.

Difficulty: EASY

Starter code:

Solutions:
import math
n = int(input())
a = n
b = n
c = n
sum = 0
for i in range(a):
	for j in range(b):
		for k in range(c):
			sum = sum + math.gcd(math.gcd(i + 1, j + 1), k + 1)
print(sum)


import math
k = int(input())
s = 0
for p in range(k):
	for q in range(k):
		g = math.gcd(p + 1, q + 1)
		for i in range(k):
			r = math.gcd(g, i + 1)
			s = s + r
print(s)


from math import gcd
k = int(input())
cnt = 0
for i in range(1, k + 1):
	for j in range(1, k + 1):
		a = gcd(i, j)
		for k in range(1, k + 1):
			cnt += gcd(a, k)
print(cnt)


from math import gcd
K = int(input())
ans = 0
r = range(1, K + 1)
for i in r:
	for j in r:
		for k in r:
			ans += gcd(gcd(i, j), k)
print(ans)


import math
k = int(input())
ans = 0
for i in range(1, k + 1):
	for j in range(1, k + 1):
		a = math.gcd(i, j)
		for l in range(1, k + 1):
			ans += math.gcd(a, l)
print(ans)


k = int(input()) + 1
from math import gcd
print(sum((gcd(gcd(i, j), r) for i in range(1, k) for j in range(1, k) for r in range(1, k))))


import math
K = int(input())
ans = 0
for i in range(1, K + 1):
	for j in range(1, K + 1):
		tmp = math.gcd(i, j)
		for n in range(1, K + 1):
			ans += math.gcd(tmp, n)
print(ans)


from math import gcd
k = int(input())
count = 0
for a in range(1, k + 1):
	for b in range(1, k + 1):
		for c in range(1, k + 1):
			count += gcd(gcd(a, b), c)
print(count)


import math
k = int(input())
total = 0
for i in range(1, k + 1):
	for j in range(1, k + 1):
		tmp = math.gcd(i, j)
		for k in range(1, k + 1):
			total += math.gcd(tmp, k)
print(total)


import math
K = int(input())
s = 0
for a in range(1, K + 1):
	for b in range(1, K + 1):
		x = math.gcd(a, b)
		for c in range(1, K + 1):
			s += math.gcd(x, c)
print(s)


from math import gcd
n = int(input())
ans = 0
for i in range(1, n + 1):
	for j in range(1, n + 1):
		x = gcd(i, j)
		for k in range(1, n + 1):
			ans += gcd(x, k)
print(ans)


import numpy as np
K = int(input())
x = np.arange(1, K + 1)
print(np.sum(np.gcd.outer(np.gcd.outer(x, x), x)))


from math import gcd
z = range(1, 1 + int(input()))
y = 0
for a in z:
	for b in z:
		for c in z:
			y += gcd(gcd(a, b), c)
print(y)


import math
K = int(input())
print(sum([math.gcd(math.gcd(i, j), k) for i in range(1, K + 1) for j in range(1, K + 1) for k in range(1, K + 1)]))


import math
N = int(input())
g1 = [math.gcd(x, y) for x in range(1, N + 1) for y in range(1, N + 1)]
g2 = [math.gcd(x, y) for x in g1 for y in range(1, N + 1)]
print(sum(g2))


import math
N = int(input()) + 1
sum = 0
for i in range(1, N):
	for j in range(1, N):
		tmp = math.gcd(i, j)
		for k in range(1, N):
			sum += math.gcd(tmp, k)
print(sum)


import math
k = int(input())
l = [math.gcd(i, j) for j in range(1, k + 1) for i in range(1, k + 1)]
o = 0
for i in l:
	for j in range(1, k + 1):
		o += math.gcd(i, j)
print(o)


from math import gcd
k = int(input())
ans = 0
for p in range(1, k + 1):
	for q in range(1, k + 1):
		for r in range(1, k + 1):
			ans += gcd(p, gcd(q, r))
print(ans)


import math
ans = 0
K = int(input())
for a in range(1, K + 1):
	for b in range(1, K + 1):
		for c in range(1, K + 1):
			ans += math.gcd(a, math.gcd(b, c))
print(ans)


from sys import stdin, stdout
import math

def main():
	k = int(stdin.readline().rstrip())
	ans = 0
	for a in range(1, k + 1):
		for b in range(1, k + 1):
			ab = math.gcd(a, b)
			for c in range(1, k + 1):
				ans = ans + math.gcd(ab, c)
	stdout.write(str(ans))
	stdout.write('\n')
main()


import math
x = 0
y = 0
K = int(input())
for i in range(1, K + 1):
	for j in range(1, K + 1):
		y = math.gcd(i, j)
		for h in range(1, K + 1):
			x = x + math.gcd(y, h)
print(x)


import math
n = int(input())
c = 0
for i in range(1, n + 1):
	for j in range(1, n + 1):
		d = math.gcd(i, j)
		for k in range(1, n + 1):
			c += math.gcd(d, k)
print(c)


import math
n = int(input())
ans = 0
for i in range(1, n + 1):
	for j in range(1, n + 1):
		r = math.gcd(i, j)
		for k in range(1, n + 1):
			ans += math.gcd(r, k)
print(ans)


from itertools import product
from math import gcd
K = int(input())
print(sum([gcd(gcd(a, b), c) for (a, b, c) in product(range(1, K + 1), repeat=3)]))


import math
k = int(input())
print(sum((math.gcd(math.gcd(a, b), c) for a in range(1, k + 1) for b in range(1, k + 1) for c in range(1, k + 1))))


import math
K = int(input())
r = range(1, K + 1)
print(sum((math.gcd(math.gcd(a, b), c) for a in r for b in r for c in r)))


import math
n = int(input())
ans = [math.gcd(i + 1, math.gcd(j + 1, k + 1)) for i in range(n) for j in range(n) for k in range(n)]
print(sum(ans))


import sys
from collections import deque, defaultdict, Counter
from itertools import accumulate, product, permutations, combinations
from operator import itemgetter
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush
from math import ceil, floor, sqrt, gcd, inf
from copy import deepcopy
import numpy as np
import scipy as sp
INF = inf
MOD = 1000000007
k = int(input())
tmp = [[0 for i in range(k + 1)] for j in range(k + 1)]
res = 0
for i in range(1, k + 1):
	for j in range(1, k + 1):
		tmp[i][j] = gcd(i, j)
for a in range(1, k + 1):
	for b in range(k + 1):
		for c in range(k + 1):
			res += tmp[tmp[a][b]][c]
print(res)


from math import gcd
k = int(input())
ans = 0
for i in range(1, k + 1):
	for j in range(1, k + 1):
		ij = gcd(i, j)
		for m in range(1, k + 1):
			ans += gcd(ij, m)
print(ans)


k = int(input())
s = 0
from math import gcd
for a in range(1, k + 1):
	for b in range(1, k + 1):
		for c in range(1, k + 1):
			d = gcd(a, b)
			s += gcd(d, c)
print(s)


import math
n = int(input())
s = 0
for i in range(1, n + 1):
	for j in range(1, n + 1):
		for k in range(1, n + 1):
			s += math.gcd(i, math.gcd(j, k))
print(s)


from math import gcd
a = 0
K = int(input())
for i in range(1, K + 1):
	for j in range(1, K + 1):
		for l in range(1, K + 1):
			a += gcd(i, gcd(j, l))
print(a)


import math
from itertools import combinations_with_replacement as comb
from functools import reduce

def main():
	K = int(input())
	ans = 0
	for abc in comb(range(1, K + 1), 3):
		gcd = reduce(math.gcd, abc)
		s = len(set(abc))
		if s == 1:
			k = 1
		elif s == 2:
			k = 3
		else:
			k = 6
		ans += gcd * k
	print(ans)

def __starting_point():
	main()
__starting_point()


import collections

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
K = int(input())
cnt = collections.defaultdict(int)
for a in range(1, K + 1):
	for b in range(1, K + 1):
		cnt[gcd(a, b)] += 1
ans = 0
for c in range(1, K + 1):
	for gcd_of_ab in cnt.keys():
		ans += gcd(gcd_of_ab, c) * cnt[gcd_of_ab]
print(ans)


from math import gcd
K = int(input())
S = 0
for i in range(1, K + 1):
	for j in range(1, K + 1):
		for k in range(1, K + 1):
			S += gcd(gcd(i, j), k)
print(S)


from math import gcd
K = int(input())
N = range(1, K + 1)
print(sum([gcd(gcd(a, b), c) for a in N for b in N for c in N]))


from math import gcd

def main():
	K = int(input())
	ans = 0
	for i in range(1, K + 1):
		for j in range(1, K + 1):
			temp = gcd(i, j)
			for l in range(1, K + 1):
				ans += gcd(temp, l)
	print(ans)

def __starting_point():
	main()
__starting_point()


import sys
from math import ceil as C, floor as F, sqrt, gcd as G
from collections import defaultdict as D, Counter as CNT
from functools import reduce as R
import heapq as HQ

class Heap:

	def __init__(self, data, reverse=False):
		self.reverse = -1 if reverse else 1
		self.data = [self.reverse * d for d in data]
		HQ.heapify(self.data)

	def push(self, x):
		return HQ.heappush(self.data, self.reverse * x)

	def pop(self):
		return self.reverse * HQ.heappop(self.data)
ALP = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
alp = 'abcdefghijklmnopqrstuvwxyz'

def _X():
	return sys.stdin.readline().rstrip().split(' ')

def _S(ss):
	return tuple(ss) if len(ss) > 1 else ss[0]

def S():
	return _S(_X())

def Ss():
	return list(S())

def _I(ss):
	return tuple([int(s) for s in ss]) if isinstance(ss, tuple) else int(ss)

def I():
	return _I(S())

def _Is(ss):
	return list(ss) if isinstance(ss, tuple) else [ss]

def Is():
	return _Is(I())
n = I()
ans = 0
for i in range(1, n + 1):
	for j in range(1, n + 1):
		for k in range(1, n + 1):
			ans += G(i, G(j, k))
print(ans)


import math
k = int(input())
ans = 0
for i in range(1, k + 1):
	for j in range(1, k + 1):
		b = math.gcd(i, j)
		for k in range(1, k + 1):
			ans += math.gcd(b, k)
print(ans)


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
k = int(input())
ans = 0
for a in range(1, k + 1):
	for b in range(a, k + 1):
		for c in range(b, k + 1):
			d = gcd(a, b)
			if len({a, b, c}) == 1:
				ans += gcd(c, d)
			elif len({a, b, c}) == 2:
				ans += 3 * gcd(c, d)
			else:
				ans += 6 * gcd(c, d)
print(ans)


k = int(input())
from math import gcd
ans = 0
for i in range(1, k + 1):
	for j in range(1, k + 1):
		for s in range(1, k + 1):
			ans += gcd(gcd(i, j), s)
print(ans)


import math
k = int(input())
ans = 0
for a in range(1, k + 1):
	for b in range(a + 1, k + 1):
		ans += math.gcd(a, b)
		for c in range(b + 1, k + 1):
			ans += math.gcd(math.gcd(a, b), c)
ans *= 6
ans += (k + 1) * k / 2
print(int(ans))


import math
k = int(input())
ans = 0
for a in range(1, k + 1):
	for b in range(1, k + 1):
		tmp = math.gcd(a, b)
		for c in range(1, k + 1):
			ans += math.gcd(tmp, c)
print(ans)


from math import gcd
n = int(input())
l = [gcd(i + 1, gcd(j + 1, k + 1)) for i in range(n) for j in range(n) for k in range(n)]
print(sum(l))


import math
k = int(input())
s = 0
for a in range(1, k + 1):
	for b in range(1, k + 1):
		gcdab = math.gcd(a, b)
		if gcdab == 1:
			s += k
		else:
			for c in range(1, k + 1):
				s += math.gcd(gcdab, c)
print(s)


import math
K = int(input())
c = 0
for i in range(1, K + 1):
	for j in range(1, K + 1):
		for k in range(1, K + 1):
			c += math.gcd(math.gcd(i, j), k)
print(c)


from math import gcd
k = int(input())
ans = 0
for x in range(1, k + 1):
	for y in range(1, k + 1):
		for z in range(1, k + 1):
			ans += gcd(gcd(x, y), z)
print(ans)


from math import gcd
k = int(input())
r = range(1, k + 1)
ans = sum([gcd(gcd(a, b), c) for a in r for b in r for c in r])
print(ans)


from math import gcd as g
k = int(input())
ans = 0
for a in range(1, k + 1):
	for b in range(1, k + 1):
		temp = g(a, b)
		for c in range(1, k + 1):
			ans += g(temp, c)
print(ans)


from math import gcd

def answer(k: int) -> int:
	result = 0
	for a in range(1, k + 1):
		for b in range(1, k + 1):
			temp = gcd(a, b)
			for c in range(1, k + 1):
				result += gcd(temp, c)
	return result

def main():
	k = int(input())
	print(answer(k))

def __starting_point():
	main()
__starting_point()


from math import gcd
K = int(input()) + 1
gcd_list = [gcd(m, gcd(k, l)) for k in range(1, K) for l in range(1, K) for m in range(1, K)]
print(sum(gcd_list))


import math as M
k = int(input())
s = 0
for a in range(1, k + 1):
	for b in range(1, k + 1):
		for c in range(1, k + 1):
			s += M.gcd(M.gcd(a, b), c)
print(s)


import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
import numpy as np

def main():
	k = int(input())
	k2 = np.arange(1, k + 1)
	k2gcd = np.gcd.outer(k2, np.gcd.outer(k2, k2))
	print(k2gcd.sum())

def __starting_point():
	main()
__starting_point()


from math import gcd
k = int(input())
ans = 0
for i in range(1, k + 1):
	for j in range(1, k + 1):
		ans_ = gcd(i, j)
		for l in range(1, k + 1):
			ans += gcd(ans_, l)
print(ans)


from math import gcd
from functools import reduce
k = int(input())
z = range(1, k + 1)
print(sum((gcd(i, gcd(j, k)) for i in z for j in z for k in z)))


K = int(input())
import math
i = 0
l = list(range(K + 1))[1:]
for a in l:
	for b in l:
		for c in l:
			i += math.gcd(math.gcd(a, b), c)
print(i)


[print(sum([g(g(i, j), k) for g in [__import__('math').gcd] for n in [int(input())] for r in [range(1, n + 1)] for i in r for j in r for k in r]))]


from math import gcd
K = int(input())
result = 0
for a in range(1, K + 1):
	for b in range(1, K + 1):
		for c in range(1, K + 1):
			result += gcd(gcd(a, b), c)
print(result)


k = int(input())
import math
s = 0
result = 0
for a in range(1, k + 1, 1):
	for b in range(a, k + 1, 1):
		for c in range(b, k + 1, 1):
			gcd = math.gcd(math.gcd(a, b), math.gcd(b, c))
			if a == b == c:
				pass
			elif a == b and b != c or (b == c and b != a) or (a == c and a != c):
				gcd = 3 * gcd
			else:
				gcd = 6 * gcd
			result += gcd
print(result)


from math import gcd
N = int(input())
c = 0
for i in range(1, N + 1):
	for j in range(1, N + 1):
		for k in range(1, N + 1):
			c += gcd(i, gcd(j, k))
print(c)


from math import *
from itertools import *
r = range(1, int(input()) + 1)
print(sum((gcd(a, gcd(b, c)) for (a, b, c) in product(r, r, r))))


import math
from functools import reduce
k = int(input())
ans = 0
gcd_sum = [0] * 201
for i in range(1, k + 1):
	for j in range(1, k + 1):
		gcd_sum[i] += math.gcd(i, j)
for a in range(1, k + 1):
	for b in range(1, k + 1):
		_gcd = math.gcd(a, b)
		ans += gcd_sum[_gcd]
print(ans)


import sys

def main():
	N = int(sys.stdin.readline())

	def gcd(a, b):
		if b == 0:
			return a
		return gcd(b, a % b)
	num_cnt_dic = {}
	num_gcd = [[0] * (N + 1) for _ in range(N + 1)]
	for i in range(1, N + 1):
		for j in range(1, N + 1):
			g = gcd(i, j)
			num_cnt_dic[g] = num_cnt_dic.get(g, 0) + 1
			num_gcd[i][j] = g
	ans = 0
	for i in list(num_cnt_dic.keys()):
		for j in range(1, N + 1):
			ans += num_gcd[i][j] * num_cnt_dic[i]
	print(ans)

def __starting_point():
	main()
__starting_point()


import math
K = int(input())
sum = 0
for a in range(1, K + 1):
	for b in range(1, K + 1):
		d = math.gcd(a, b)
		for c in range(1, K + 1):
			sum += math.gcd(c, d)
print(sum)


n = int(input())
l = 0
import math
for a in range(1, n + 1):
	for b in range(1, n + 1):
		for c in range(1, n + 1):
			l += math.gcd(a, math.gcd(b, c))
print(l)


from math import gcd
k = int(input())
ans = 0
for s in range(1, k + 1):
	for t in range(1, k + 1):
		for u in range(1, k + 1):
			ans += gcd(gcd(s, t), u)
print(ans)


from math import gcd
K = int(input())
g = 0
for a in range(1, K - 1):
	for b in range(a + 1, K):
		for c in range(b + 1, K + 1):
			g += gcd(gcd(a, b), c) * 6
for d in range(1, K):
	for e in range(d + 1, K + 1):
		g += gcd(d, e) * 6
g += K * (K + 1) // 2
print(g)


import math
k = int(input())
a = 0
for i in range(1, k + 1):
	for j in range(1, k + 1):
		for h in range(1, k + 1):
			a += math.gcd(math.gcd(i, j), h)
print(a)


import math as mt
import itertools as iters
K = int(input())
A = 0
for (a, b, c) in iters.product(range(1, K + 1), repeat=3):
	A += mt.gcd(a, mt.gcd(b, c))
print(A)


import math
N = int(input())
all_gcd = [math.gcd(math.gcd(i, j), m) for i in range(1, N + 1) for j in range(1, N + 1) for m in range(1, N + 1)]
print(sum(all_gcd))


import math
s = 0
k = int(input())
for i in range(k, 0, -1):
	for j in range(k, 0, -1):
		d = math.gcd(i, j)
		for h in range(k, 0, -1):
			s += math.gcd(d, h)
print(s)


import math
K = int(input())
ans = 0
for a in range(1, K + 1):
	for b in range(a, K + 1):
		for c in range(b, K + 1):
			s = math.gcd(a, b)
			t = math.gcd(s, c)
			if a == c:
				ans += t
			elif (a == b or b == c) and a != c:
				ans += 3 * t
			else:
				ans += 6 * t
print(ans)


import math
K = int(input())
rst = 0
for i in range(1, K + 1):
	for j in range(1, K + 1):
		tmp = math.gcd(i, j)
		for k in range(1, K + 1):
			rst += math.gcd(tmp, k)
print(rst)


from math import gcd
k = int(input())
ans = 0
for l in range(1, k + 1):
	for m in range(1, k + 1):
		for n in range(1, k + 1):
			ans += gcd(l, gcd(m, n))
print(ans)


n = int(input())
from math import *
r = range(1, n + 1)
a = 0
for i in r:
	for j in r:
		g = gcd(i, j)
		for k in r:
			h = gcd(g, k)
			a += h
print(a)


from math import gcd as g
r = range(1, int(input()) + 1)
s = 0
for i in r:
	for j in r:
		for k in r:
			s += g(g(i, j), k)
print(s)


k = int(input())
ans = 0

def gcd(a, b):
	if a % b == 0:
		return b
	c = a % b
	return gcd(b, c)
for l in range(1, k + 1):
	for m in range(l, k + 1):
		for n in range(m, k + 1):
			tmp1 = gcd(l, n)
			tmp2 = gcd(tmp1, m)
			if l == m == n:
				ans += tmp2
			elif l == m or m == n:
				ans += 3 * tmp2
			else:
				ans += 6 * tmp2
print(ans)


from math import gcd
N = int(input())
ans = sum([gcd(gcd(i, j), k) for i in range(1, N + 1) for j in range(1, N + 1) for k in range(1, N + 1)])
print(ans)


import math
k = int(input())
ans = 0
for i in range(1, k + 1):
	for j in range(1, k + 1):
		ab = math.gcd(i, j)
		for x in range(1, k + 1):
			ans += math.gcd(ab, x)
print(ans)


import math
N = int(input())
ans = 0
for i in range(1, N + 1):
	for j in range(i, N + 1):
		for k in range(j, N + 1):
			if i == j and j == k:
				ans += i
			elif i < j and j < k:
				ans += 6 * math.gcd(i, math.gcd(j, k))
			else:
				ans += 3 * math.gcd(i, math.gcd(j, k))
print(ans)


from math import gcd
K = int(input())
k = [1, 1, 1]
g = 0
for a in range(1, K + 1):
	for b in range(1, K + 1):
		for c in range(1, K + 1):
			g += gcd(gcd(a, b), c)
print(g)


from math import gcd
N = int(input())
ans = 0
for a in range(1, N + 1):
	for b in range(1, N + 1):
		for c in range(1, N + 1):
			ans += gcd(a, gcd(b, c))
print(ans)


def gcd_r(a, b):
	if memo[a][b] != 0:
		return memo[a][b]
	if a < b:
		(a, b) = (b, a)
	memo[a][b] = gcd(a, b)
	memo[b][a] = memo[a][b]
	return memo[a][b]

def gcd(a, b):
	r = a % b
	if r == 0:
		return b
	return gcd(b, r)
k = int(input())
memo = [[0] * (k + 1) for _ in range(k + 1)]
total = 0
for i in range(1, k + 1, 1):
	for c in range(1, k + 1, 1):
		total += gcd_r(gcd_r(i, i), c)
for a in range(1, k + 1, 1):
	for b in range(a + 1, k + 1, 1):
		for c in range(1, k + 1, 1):
			total += gcd_r(gcd_r(a, b), c) * 2
print(total)


import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
input = sys.stdin.readline

def RD():
	return input().rstrip()

def F():
	return float(input().rstrip())

def I():
	return int(input().rstrip())

def MI():
	return map(int, input().split())

def MF():
	return map(float, input().split())

def LI():
	return list(map(int, input().split()))

def TI():
	return tuple(map(int, input().split()))

def LF():
	return list(map(float, input().split()))

def Init(H, W, num):
	return [[num for i in range(W)] for j in range(H)]
gcd = math.gcd

def main():
	K = I()
	ans = 0
	for i in range(1, K + 1):
		for j in range(i, K + 1):
			temp = gcd(i, j)
			for k in range(j, K + 1):
				n = set([i, j, k])
				n = len(n)
				ans += gcd(temp, k) * (n + 1) * n // 2
	print(ans)

def __starting_point():
	main()
__starting_point()


from math import gcd
K = int(input())
ans = 0
for i in range(1, K + 1):
	for j in range(1, K + 1):
		tmp = gcd(i, j)
		if tmp == 1:
			ans += tmp * K
		else:
			for k in range(1, K + 1):
				ans += gcd(tmp, k)
print(ans)


import math
K = int(input())
ans = []
bc = [math.gcd(b, c) for b in range(1, K + 1) for c in range(1, K + 1)]
for a in range(1, K + 1):
	for i in bc:
		x = math.gcd(a, i)
		ans.append(x)
print(sum(ans))


n = int(input())
memo = [[0] * (n + 1) for x in range(n + 1)]

def gcd(x, y):
	if y == 0:
		return x
	if not memo[x][y] == 0:
		return memo[x][y]
	memo[x][y] = gcd(y, x % y)
	return gcd(y, x % y)
res = 0
for i in range(1, n + 1):
	for j in range(1, n + 1):
		q = gcd(i, j)
		if q == 1:
			res += n
		else:
			for k in range(1, n + 1):
				p = gcd(q, k)
				res += p
print(res)


import math
k = int(input())
r = 0
ls = []
for i in range(k):
	for j in range(k):
		a = math.gcd(i + 1, j + 1)
		for l in range(k):
			r += math.gcd(a, l + 1)
print(r)


import math
K = int(input())
S = 0
for i in range(1, K + 1):
	for j in range(1, K + 1):
		for l in range(1, K + 1):
			S = S + math.gcd(l, math.gcd(j, i))
print(S)


from collections import defaultdict
from math import gcd

def answer(k: int) -> int:
	dd = defaultdict(int)
	for a in range(1, k + 1):
		for b in range(1, k + 1):
			dd[gcd(a, b)] += 1
	gcd_sum = 0
	for c in range(1, k + 1):
		for gcd_ab in dd.keys():
			gcd_sum += gcd(gcd_ab, c) * dd[gcd_ab]
	return gcd_sum

def main():
	k = int(input())
	print(answer(k))

def __starting_point():
	main()
__starting_point()


K = int(input())
ans = 0

def gcd(x, y):
	if x == 1 or y == 1:
		return 1
	else:
		while True:
			if x >= y:
				x %= y
			else:
				y %= x
			if x == 0 or y == 0:
				break
		return x + y
for i in range(1, K + 1):
	for j in range(i, K + 1):
		for k in range(j, K + 1):
			if i == j == k:
				ans += gcd(i, gcd(j, k))
			elif i == j or j == k or k == i:
				ans += gcd(i, gcd(j, k)) * 3
			else:
				ans += gcd(i, gcd(j, k)) * 6
print(ans)


K = int(input())

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
result = 0
for a in range(1, K + 1):
	result += a
	b = a + 1
	while b <= K:
		result += 6 * gcd(a, b)
		l = gcd(a, b)
		c = b + 1
		while c <= K:
			result += 6 * gcd(l, c)
			c += 1
		b += 1
print(result)


import math as f
a = int(input())
ans = 0
for i in range(1, a + 1):
	for j in range(1, a + 1):
		for k in range(1, a + 1):
			b = f.gcd(i, j)
			ans += f.gcd(b, k)
print(ans)


import math
from functools import reduce

def gcd(*numbers):
	return reduce(math.gcd, numbers)

def gcd_list(numbers):
	return reduce(math.gcd, numbers)
k = int(input())
p = 0
ans = 0
if k > 2:
	for i in range(1, k - 1):
		for j in range(i + 1, k):
			for m in range(j + 1, k + 1):
				ans += gcd(i, j, m)
p += 6 * ans
b = 0
for i in range(1, k):
	for j in range(i + 1, k + 1):
		b += math.gcd(i, j)
p += 6 * b + k * (k + 1) // 2
print(p)


def main():
	import math
	k = int(input())
	cand = [int(v) for v in range(1, k + 1)]
	ans = 0
	for i in range(1, k + 1):
		for j in range(1, k + 1):
			for l in range(1, k + 1):
				temp = math.gcd(i, j)
				res = math.gcd(temp, l)
				ans += res
	return ans

def __starting_point():
	print(main())
__starting_point()


import math
k = int(input())
ans = 0
for a in range(1, k + 1):
	for b in range(a, k + 1):
		for c in range(b, k + 1):
			gcd = math.gcd(math.gcd(a, b), c)
			if a == b == c:
				ans += gcd
			elif a == b or b == c:
				ans += gcd * 3
			else:
				ans += gcd * 6
print(ans)


import math
k = int(input())
total = 0
for x in range(1, k + 1):
	for y in range(x, k + 1):
		for z in range(y, k + 1):
			if x == y == z:
				total += x
			elif x == y or y == z:
				total += 3 * math.gcd(math.gcd(x, y), z)
			else:
				total += 6 * math.gcd(math.gcd(x, y), z)
print(total)


k = int(input())

def gcd1(a, b):
	while True:
		if a < b:
			(a, b) = (b, a)
		c = a % b
		if c == 0:
			return b
		else:
			a = b
			b = c

def gcd2(a, b, c):
	tmp = gcd1(a, b)
	ans = gcd1(tmp, c)
	return ans
count = 0
for i in range(k):
	for j in range(i, k):
		for l in range(j, k):
			tmp = gcd2(i + 1, j + 1, l + 1)
			if i == j == l:
				count = count + tmp
			elif i == j or j == l:
				count = count + tmp * 3
			else:
				count = count + tmp * 6
print(count)


import math
K = int(input())
list1 = []
s = 1
while s <= K:
	list1.append(s)
	s = s + 1
list3 = []
t = 1
while t <= K * K:
	list3.append(t)
	t = t + 1
list2 = []
k = 1
for i in list1:
	for j in list1:
		X = math.gcd(i, j)
		list2.append(X)
Y = 0
for k in list1:
	for l in list3:
		Y = Y + math.gcd(k, list2[l - 1])
print(Y)


import math
k = int(input())
l = range(1, k + 1)
print(sum([math.gcd(x, math.gcd(y, z)) for x in l for y in l for z in l]))


k = int(input())

def gcd1(a, b):
	while True:
		if a < b:
			(a, b) = (b, a)
		c = a % b
		if c == 0:
			return b
		else:
			a = b
			b = c
count = 0
for i in range(k):
	for j in range(k):
		tmp = gcd1(i + 1, j + 1)
		if tmp == 1:
			count = count + k
		else:
			for l in range(k):
				tmp2 = gcd1(tmp, l + 1)
				count = count + tmp2
print(count)


n = int(input())
res = 0
from math import *
for i in range(1, n + 1):
	for j in range(1, n + 1):
		for k in range(1, n + 1):
			res += gcd(gcd(i, j), k)
print(res)


K = int(input())
ans = 0

def gcd(x, y):
	if x % y == 0:
		return y
	else:
		return gcd(y, x % y)
ans = 0
for a in range(1, K + 1):
	for b in range(1, K + 1):
		d = gcd(a, b)
		for c in range(1, K + 1):
			ans += gcd(c, d)
print(ans)


K = int(input())
ans = 0

def gcd(x, y):
	if y == 0:
		return x
	if x >= y:
		return gcd(y, x % y)
	if x < y:
		return gcd(x, y % x)
for i in range(1, K + 1):
	ans += i
for i in range(1, K + 1):
	for j in range(i + 1, K + 1):
		ans += gcd(i, j) * 6
for i in range(1, K + 1):
	for j in range(i + 1, K + 1):
		for k in range(j + 1, K + 1):
			ans += gcd(gcd(i, j), k) * 6
print(ans)


import math

def resolve():
	k = int(input())
	ans = 0
	for a in range(1, k + 1):
		for b in range(1, k + 1):
			for c in range(1, k + 1):
				ans += math.gcd(math.gcd(a, b), c)
	print(ans)
resolve()


import math
l = int(input())
s = 0
for i in range(1, l + 1):
	for j in range(1, l + 1):
		t = math.gcd(i, j)
		for k in range(1, l + 1):
			s += math.gcd(t, k)
print(s)


import itertools as itt
import math
k = int(input())
ans = 0
for i in itt.combinations_with_replacement(range(1, k + 1), 3):
	if i[0] == i[1] and i[0] != i[2]:
		ans += 3 * math.gcd(math.gcd(i[0], i[1]), i[2])
	elif i[1] == i[2] and i[1] != i[0]:
		ans += 3 * math.gcd(math.gcd(i[0], i[1]), i[2])
	elif i[0] == i[1] and i[0] == i[2]:
		ans += math.gcd(math.gcd(i[0], i[1]), i[2])
	else:
		ans += 6 * math.gcd(math.gcd(i[0], i[1]), i[2])
print(ans)


from math import gcd
m = gcd
f = 0
n = int(input())
for i in range(1, n + 1):
	for j in range(1, n + 1):
		for k in range(1, n + 1):
			f += m(i, m(j, k))
print(f)


import math
k = int(input())
wa = 0
aa = 0
for i in range(1, k + 1):
	for j in range(1, k + 1):
		aa = math.gcd(i, j)
		for l in range(1, k + 1):
			wa += math.gcd(aa, l)
print(wa)


import math
n = int(input())
m = math.gcd
a = 0
for i in range(1, n + 1):
	for j in range(1, n + 1):
		for k in range(1, n + 1):
			a += m(m(i, j), k)
print(a)


from math import gcd
k = int(input())
sum = 0
for a in range(1, k + 1):
	for b in range(1, k + 1):
		x = gcd(a, b)
		for c in range(1, k + 1):
			sum += gcd(x, c)
print(sum)


from math import gcd

def main():
	k = int(input())
	ans = 0
	for i in range(1, k + 1):
		for j in range(1, k + 1):
			for k in range(1, k + 1):
				ans += gcd(gcd(i, j), k)
	print(ans)

def __starting_point():
	main()
__starting_point()


import math
N = int(input())
A = 0
for i in range(1, N + 1):
	for j in range(1, N + 1):
		for k in range(1, N + 1):
			A += math.gcd(math.gcd(i, j), k)
print(A)