Problem:


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



Sample input:
2


Sample output:
9

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def gcd(a,b):
	if b == 0:
		return a
	else:
		return gcd(b,a%b)

n = int(raw_input())
sm = 0;
for i in range(1,n+1):
  for j in range(1,n+1):
    for k in range(1,n+1):
      sm += gcd(gcd(i,j),k)
      
print(sm)

Submission status: Accepted

Solution code:
def GCD(y,x):
    if y>x:
        p,q=y,x
    else:
        p,q=x,y
    if p%q==0:
        return q
    else:
        return GCD(q,p%q)

ans1=0
ans2=0
ans3=0
K=int(input())
for i in range(1,K+1):
    for j in range(i+1,K+1):
        for l in range(j+1,K+1):
            ans1+=GCD(GCD(i,j),l)

for i in range(1,K+1):
    for j in range(i+1,K+1):
        ans2+=GCD(i,j)

for i in range(1,K+1):
    ans3+=i
print(ans1*6+ans2*6+ans3)

Submission status: Accepted

Solution code:
import math

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 += math.gcd(math.gcd(i, j), k)

print(ans)

Submission status: Accepted

Solution code:
# 最大公約数，最小公倍数
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


dp = [[0 for _ in range(205)] for _ in range(205)]

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):
            if len(set([a, b, c])) == 1:
                ans += a
            elif len(set([a, b, c])) == 2:
                ans += gcd(a, gcd(b, c)) * 3
            else:
                ans += gcd(a, gcd(b, c)) * 6
print(ans)

Submission status: Accepted

Solution code:
import math

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

print(ans)

Submission status: Accepted

Solution code:
import math
import sys
input = sys.stdin.readline

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+=math.gcd(math.gcd(i,j),k)

print(ans)

Submission status: Accepted

Solution code:
# -*- coding- utf-8 -*-
# C - Sum of gcd of Triplets (Easy)
# モジュールのインポート
import math
import itertools
from functools import reduce

# 標準入力の取得
K = int(input())

# 求解処理
result = 0
for a,b in itertools.product(range(1, K+1), repeat=2):
    d = math.gcd(a, b)
    for c in range(1, K+1):
        result += math.gcd(d, c)

# 結果出力
print(result)

Submission status: Accepted

Solution code:
import math

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

print(ans)

Submission status: Accepted

Solution code:
def gcd(x, y):
  while(x % y != 0 and y % x != 0):
    if(x > y):
      x = x % y
    else:
      y = y % x
  if(x > y):
    return y
  else:
    return x

K = int(input())
ans = 0
for i in range(1, K+1):
  for j in range(i, K+1):
    for k in range(j, K+1):
      if(i == j and j == k):
        ans += i
      elif(i == j or j == k):
        ans += gcd(i, k) * 3
      else:
        ans += gcd(i, gcd(j, k)) * 6
print(ans)

Submission status: Accepted

Solution code:
import math

K = int(input())
total = 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):
      total += math.gcd(ab, c)
print(total)

Submission status: Accepted

Solution code:
def gcd(a,b):
    if b==0:
        return a
    return gcd(b,a%b)

k=int(input())

sum=0;

for a in range(1,k+1):
    sum+=a

for a in range(1,k+1):
    for b in range(1,a):
        sum+=gcd(a,b)*6

for a in range(1,k+1):
    for b in range(1,a):
        for c in range(1,b):
            sum+=gcd(a,gcd(b,c))*6

print(sum)

Submission status: Accepted

Solution code:
import math

ans = 0
K = int(input())
for i in range(1, K+1):
  for j in range(1, i):
    for k in range(1, j):
      ans += math.gcd(i, math.gcd(j, k)) * 6
    ans += math.gcd(i, j) * 3
  for k in range(1, i):
    ans += math.gcd(i, k) * 3
  ans += i
print(ans)

Submission status: Accepted

Solution code:
import math
N = int(input())
num_list = []
for an in range(1,N+1):
    for bn in range(1,N+1):
        for cn in range(1,N+1):
            
            a = [an,bn,cn]
            ans = a[0]
            for i in range(1,3):
                ans = math.gcd(ans, a[i])
            num_list.append(ans)
print(sum(num_list))

Submission status: Accepted

Solution code:
from math import gcd
k=0
n=int(input())
for a in range(1,n+1):
    for b in range(a,n+1):
        for c in range(b,n+1):
            l=list(set([a,b,c]))
            p=1
            for i in range(len(l)-1):
                p*=3-i
            k+=gcd(gcd(a,b),c)*p
print(k)

Submission status: Accepted

Solution code:
import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)
n = int(input())
if n == 1:
    print(1)
    exit()
if n == 2:
    print(9)
    exit()
ans = 0
for i in range(1,n - 1):
    for j in range(i + 1, n ):
        for k in range(j + 1, n + 1):
            ans += gcd(i, j, k) * 6
for i in range(1, n):
    for j in range(i + 1, n + 1):
        ans +=math.gcd(i, j) * 6

for i in range(1, n + 1):
    ans += i
print(ans)

Submission status: Accepted

Solution code:
import math

K = int(input())
ans = 0
table = []
for i in range(1, K + 1):
    for j in range(1, K + 1):
        table.append(math.gcd(i, j))

for i in table:
    for j in range(1, K + 1):
        ans += math.gcd(i, j)

print(ans)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

def gcd(u, v):
    while v:
        u, v = v, u%v
    return u

def gcds(a, b, c):
    return gcd(a, gcd(b, c))
  
s = 0
k = ni()
for i in range(1, k+1):
    for j in range(1, k+1):
        for l in range(1, k+1):
            s += gcds(i, j, l)
print(s)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math
from functools import reduce

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

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

def main(a=''):
    # 整数の入力
    a = int(input())
    a = int(a)
    # スペース区切りの整数の入力
    # b, c = map(int, input().split())
    # b, c = map(int, input())

    # # 文字列の入力
    # a = input()
    # 出力
    # print("{} {}".format(a+b+c, s))
    sum = 0
    sum_same = 0
    sum_same_2 = 0
    for i in range(1, a + 1):
        for j in range(1, a + 1):
            if i > j:
                continue
            for k in range(1, a + 1):
                if j > k:
                    continue
                # print(i,j,k,)
                if i == j == k:
                    # print('同じ')
                    sum_same += gcd(i, j, k)
                elif i==j or j==k or i==k:
                    # print('2つ同じ')
                    sum_same_2 += gcd(i, j, k)
                else:
                    # print('違う')
                    sum += gcd(i, j, k)

    print(sum*6 + sum_same + sum_same_2*3)


if __name__ == '__main__':
    # main('200')
    main()

Submission status: Accepted

Solution code:
def main():
    import math
    from functools import reduce

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

    K = int(input())
    ans = 0

    for i in range(1,K+1):
        for j in range(1,K+1):
            for l in range(1,K+1):
                ans = ans + gcd(i,j,l)
    print (ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import functools
import itertools
import math

from collections import defaultdict

k = int(input())

@functools.lru_cache(maxsize=40000)
def gcd(a, b):
    return math.gcd(a, b)

last_result = defaultdict(int)
for a, b in itertools.product(range(1, k+1), repeat=2):
    tmp = gcd(a, b)
    last_result[tmp] += 1

s = 0
for ab, count in last_result.items():
    for c in range(1, k+1):
        s += gcd(ab, c) * count

print("{}".format(s))

Submission status: Accepted

Solution code:
import math
from functools import reduce

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

k = int(input())

sum_of_gcd = 0
dict_of_gcd = {}
for a in range(k):
    for b in range(k):
        for c in range(k):
            if a == b == c:
                sum_of_gcd  += a + 1
            else:
                sum_of_gcd  += gcd((a + 1), (b + 1), (c +1))
print(sum_of_gcd)

Submission status: Accepted

Solution code:
import math

k = int(input())

gcd_list = [[0 for j in range(k)] for i in range(k)]
for i in range(k):
    for j in range(k):
        gcd_list[i][j] = math.gcd(i+1,j+1)

app_list =[0 for i in range(k)]
summation = 0

for i in range(k):
    for j in range(k):
        app_list[gcd_list[i][j]-1] += 1

for i in range(k):
    for j in range(k):
        summation += app_list[j] * gcd_list[i][j]
    
print(summation)

Submission status: Accepted

Solution code:
def gcd(a,b):
  if(a<b):
    a,b=b,a
  if(a%b==0):
    return b
  return gcd(a%b,b)

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

Submission status: Accepted

Solution code:
def gcd(a, b):
  while b:
     a, b = b, a % b
  return a

gcd_ij = []  
ans = 0
N = int(input())

for i in range(1, N+1):
    for j in range(1, N+1):
            gcd_ij.append(gcd(i, j))

for ij in gcd_ij:
    for k in range(1, N+1):
        ans += gcd(ij, k)
        
print(ans)

Submission status: Accepted

Solution code:
import functools

def euclid(a, b):
    if b == 0:
        return a
    else:
        return euclid(b, a%b)
    
def gcd(nums):
    return functools.reduce(euclid, nums)
sn =0
N = int(input())
N +=1
for x in range(1,N):
    for y in range(x,N):
        for z in range(y,N):
            if x ==y and y ==z:
                sn +=gcd([x,y,z])
            elif x ==y or y == z or z==x:
                sn +=gcd([x,y,z])*3
            else: sn +=gcd([x,y,z])*6
print(sn)

Submission status: Accepted

Solution code:
from sys import stdin
import math
# 1行だけ読むやつ

N = int(stdin.readline().rstrip().split()[0])
Sum = 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:
                Sum += i
            elif i == j or j == k or k == i:
                temp_gcd = math.gcd(i, j)
                Sum += (math.gcd(temp_gcd, k) * 3)
            else:
                Sum += (math.gcd(temp_gcd, k) * 6) 

print(Sum)

Submission status: Accepted

Solution code:
from math import gcd
K = int(input())
ans = 0

for i in range(1, K + 1):
    ans += gcd(gcd(i, i), i)
    temp = gcd(i, i)
    for j in range(1, K + 1):
        if i != j:
            ans += gcd(temp, j)*3

for i in range(1, K + 1):
    for j in range(i + 1, K + 1):
        for l in range(j + 1, K + 1):
            ans += gcd(gcd(i, j), l)*6

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
import collections
from collections import deque
from functools import reduce
import heapq
k = int(input())
#n, k = map(int, sys.stdin.readline().split())
#s = input()
#a = list(map(int, sys.stdin.readline().split()))

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

def main():
    ans = 0
    for i in range(1, k+1):
        for j in range(1, k+1):
            if gcd(i, j) == 1:
                ans += k
                continue
            for l in range(1, k+1):
                ans += gcd(i, j, l)
    print(ans)

main()

Submission status: Accepted

Solution code:
K = int(input())

from math import gcd

def g(a,b,c):
  return gcd(gcd(a,b),c)

a = 0
for i in range(1,K+1):
  for j in range(1,K+1):
    for k in range(1,K+1):
      a += g(i,j,k)

print(a)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
#from collections import defaultdict
#d = defaultdict(int)
#import fractions
import math
#import collections
#from collections import deque
#from bisect import bisect_left
K = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
s = 0
d = 0
e = 0
for a in range(1,K+1):
    for b in range(a,K+1):
        for c in range(b,K+1):
            d = math.gcd(c,b)
            e = math.gcd(a,d)
            if a == b and b == c:
                s += e
            elif a != b and b != c :
                s += 6 * e
            else:
                s += 3 * e
print(s)

Submission status: Accepted

Solution code:
gomennnasai = [1, 9, 30, 76, 141, 267, 400, 624, 885, 1249, 1590, 2208, 2689, 3411, 4248, 5248, 
6081, 7485, 8530, 10248, 11889, 13687, 15228, 17988, 20053, 22569, 25242, 28588, 31053, 35463, 38284, 42540, 46581, 50893, 55362, 61824, 65857, 71247, 76884, 84388, 89349, 97881, 103342, 111528, 120141, 128047, 134580, 146316, 154177, 164817, 174438, 185836, 194157, 207927, 218812, 233268, 245277, 257857, 268182, 288216, 299257, 313635, 330204, 347836, 362973, 383709, 397042, 416448, 434025, 456967, 471948, 499740, 515581, 536073, 559758, 583960, 604833, 633651, 652216, 683712, 709065, 734233, 754734, 793188, 818917, 846603, 874512, 909496, 933081, 977145, 1006126, 1041504, 1073385, 1106467, 1138536, 1187112, 1215145, 1255101, 1295142, 1342852, 1373253, 1422195, 1453816, 1502376, 1553361, 1595437, 1629570, 1691292, 1726717, 1782111, 1827492, 1887772, 1925853, 1986837, 2033674, 2089776, 2145333, 2197483, 2246640, 2332104, 2379085, 2434833, 2490534, 2554600, 2609625, 2693919, 2742052, 2813988, 2875245, 2952085, 3003306, 3096024, 3157249, 3224511, 3306240, 3388576, 3444609, 3533637, 3591322, 3693924, 3767085, 3842623, 3912324, 4027884, 4102093, 4181949, 4270422, 4361548, 4427853, 4548003, 4616104, 4718640, 4812789, 4918561, 5003286, 
5131848, 5205481, 5299011, 5392008, 5521384, 5610705, 5739009, 5818390, 5930196, 6052893, 6156139, 6239472, 6402720, 6493681, 6623853, 6741078, 6864016, 6953457, 7094451, 7215016, 7359936, 7475145, 7593865, 7689630, 7886244, 7984165, 8130747, 8253888, 8403448, 8523897, 8684853, 8802826, 8949612, 9105537, 9267595, 9376656, 9574704, 9686065, 9827097, 9997134, 10174780, 10290813, 10493367, 10611772, 10813692]

k = int(input())
print(gomennnasai[k-1])

Submission status: Accepted

Solution code:
def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a

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):
            #print(a,b,c)
            #print(len(set([a,b,c])))
            abc_set = list(set([a,b,c]))
            l = len(abc_set)
            if l== 1:
                ans += a
            elif l == 2:
                ans += 3 * gcd(abc_set[0],abc_set[1])
            elif l == 3:
                ans += 6 * gcd(gcd(a,b),c)
print(ans)

Submission status: Accepted

Solution code:
k = int(input())
import math
ans = 0
ans += int((1+k)*k/2)

if k >= 2:
    for i in range(1,k+1):
        for j in range(1,k+1):
            if i != j:
                tmp = math.gcd(i,j)
                ans += math.gcd(tmp,j)*3
if k >= 3:
    for i in range(1,k-1):
        for j in range(i+1,k):
            for l in range(j+1,k+1):
                tmp = math.gcd(i,j)
                ans += math.gcd(tmp,l)*6
                    
print(ans)

Submission status: Accepted

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

from math import gcd
k = inn()
sm = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        g = gcd(i,j)
        if g==1:
            sm += k
        else:
            for m in range(1,k+1):
                sm += gcd(g,m)
print(sm)

Submission status: Accepted

Solution code:
import math
from functools import reduce


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


K = int(input())

Sum = 0

for i in range(1, K + 1):
    for j in range(1, K + 1):
        for k in range(1, K + 1):
            Sum += gcd(i, j, k)

print(Sum)

Submission status: Accepted

Solution code:
from math import gcd
K = int(input())



res = 0
for a in range(1, K+1):
    for b in range(1, K+1):
        tmp = gcd(a, b)
        for c in range(1, K+1):
            res += gcd(tmp, c)
            
print(res)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from math import gcd

def solve():
    K = int(input())
    M = [[gcd(i,j) for j in range(K+1)] for i in range(K+1)]
    res = sum(M[j][k] for m in M[1:] for j in m[1:] for k in range(1,K+1))
    return str(res)


if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
import math
n = int(input())
if n == 1:
    print(1)
else:
    sum = 0
    for i in range(1,n+1):
        for j in range(1,n+1):
            for k in range(1,n+1):
                sum += math.gcd(math.gcd(i,j),k)
    print(sum)

Submission status: Accepted

Solution code:
import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)
ans = 0
k = int(input())
for i in range(k):
    for j in range(i,k):
        for l in range(j,k):
            if i!=j and j!=l and l!=i:
                ans += gcd(i+1,j+1,l+1)*6
            elif i == j and j ==l and l ==i:
                ans += gcd(i+1,j+1,l+1)
            else:
                ans += gcd(i+1,j+1,l+1)*3
print(ans)

Submission status: Accepted

Solution code:
import math
from functools import reduce
 
def gcd(*num):
    return reduce(math.gcd,num)
 
K = int(input())
sum = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            sum += gcd(i,j,k)
print(sum)

Submission status: Accepted

Solution code:
import math

k = int(input())

x = 0

for a in range(1, k+1):
    for b in range(1, k+1):
        t = math.gcd(a, b)
        for c in range(1, k+1):
            x += math.gcd(t, c)
            
print(x)

Submission status: Accepted

Solution code:
k = int(input())

def gcd1(a, b):
    while b:
        a, b = b, a % b
    return a

ans = 0

for a in range(1,k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            g1=gcd1(a,b)
            ans += gcd1(g1,c)
            
print(ans)

Submission status: Accepted

Solution code:
from math import gcd

k=int(input())
l = [[gcd(i,j) for j in range(1, k+1)] for i in range(1, k+1)]

ans = 0
for i in range(k):
    for j in range(k):
        n = l[i][j]
        ans += sum(l[n-1])

print(ans)

Submission status: Accepted

Solution code:
import math
from functools import reduce
K = int(input())

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


ans = 0
#count = 0
for i in range(1, K + 1):
  for j in range(i, K + 1):
    for k in range(j, K + 1):
      #count += 1
      #print(count, gcd3(i, j, k))
      x = gcd(i, j, k)
      if i == j:
        if j == k:
          ans += x
        else:
          ans += 3 * x
      else:
        if i == k:
          ans += 3 * x
        elif j == k:
          ans += 3 * x
        else:
          ans += 6 * x
          

print(ans)

Submission status: Accepted

Solution code:
import math

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

Submission status: Accepted

Solution code:
import math
from functools import reduce

K = int(input())
def gcd(numbers):
        res = reduce(math.gcd, numbers)
        n = len(set(numbers))
        if n == 1:
            return res
        elif n == 2:
            return res * 3
        else:
            return res * 6

ans = 0
for a in range(1, K+1):
    for b in range(a, K+1):
        for c in range(b, K+1):
            ans += gcd([a, b, c])

print(ans)

Submission status: Accepted

Solution code:
k = int(input())
ans = 0
import math
for i in range(1, k + 1):
    for j in range(i + 1, k + 1):
        for g in range(j + 1, k + 1):
            u = math.gcd(i, j)
            w = math.gcd(u, g)
            ans += w * 6
            
for i in range(1, k + 1):
    for j in range(i + 1, k + 1):
        u = math.gcd(i, j)
        ans += u * 6
        
for i in range(1, k + 1):
    ans += i
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8

import sys
import math
import collections
import itertools
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def lcm(x, y) : return (x * y) // math.gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")

from functools import lru_cache

@lru_cache(maxsize=INF)
def ggcd(a, b):
    return math.gcd(a, b)

K = I()

h = [0] * 201
for a in range(1, K+1):
    for b in range(1, K+1):
        h[ggcd(min(a,b), max(a,b))] += 1

ans = 0
for c in range(1, K+1):
    for i, ab in enumerate(h):
        if ab != 0:
            ans += ggcd(min(c,i), max(c,i)) * ab

print(ans)

Submission status: Accepted

Solution code:
import math

k = int(input())
ans = 0
klist = list(range(1,k+1))
for ka in klist:
    for kb in klist:
        _gcd = math.gcd(ka, kb)
        for kc in klist:
            ans += math.gcd(_gcd, kc)

print(ans)

Submission status: Accepted

Solution code:
K = int(input())
def gcd(x, y):
  a, b = x, y
  while b != 0:
    a, b = b, a % b
  return a
gcds = [[0 for j in range(K)] for i in range(K)]
for i in range(K):
  for j in range(K):
    gcds[i][j] = gcd(i+1, j+1)
S = 0
for i in range(K):
  for j in range(K):
    for k in range(K):
      S += gcds[gcds[j][k]-1][i]
print(S)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
import math
n = int(input())
s= n**2+n*(n-1)+(n-1)**2
for i in range(2,n+1):
    for j in range(2,n+1):
        x = math.gcd(i,j)
        if x==1:
            s+=n-1
        else:
            for k in range(2,n+1):
                s+=math.gcd(k,x)
print(s)

Submission status: Accepted

Solution code:
from math import gcd
k = int(input())
n = 0
combi = []
for a in range(k-2):
    for b in range(a+1,k-1):
        for c in range(b+1,k):
            n += gcd(a+1,gcd(b+1,c+1)) * 3*2

for a in range(k):
    n += a+1

for a in range(k-1):
    for b in range(a+1,k):
        n += gcd(a+1,b+1) * 3 *2
            

print(n)

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import permutations
# from math import gcd

def gcd(a, b):
    # ユークリッドの互除法による最大公約数
    if b == 0:
        return a
    return gcd(b, a % b)


def make_key2(i, j):
    return '-'.join([str(val) for val in sorted([i, j])])


def make_key3(i, j, k):
    return '-'.join([str(val) for val in sorted([i, j, k])])


if __name__ == '__main__':
    K = int(input())
    ans = 0
    mem2 = defaultdict()
    mem3 = defaultdict()
    for i in range(1, K + 1):
        for j in range(i, K + 1):
            for k in range(j, K + 1):

                set_ijk = list(set([i,j,k]))
                if len(set_ijk) == 1:
                    ans += i

                elif len(set_ijk) == 2:
                    key2 = make_key2(*set_ijk)
                    if key2 in mem2:
                        gcd1 = mem2[key2]
                    else:
                        gcd1 = gcd(*set_ijk)
                        mem2[key2] = gcd1
                    ans += gcd1 * 3
                else:
                    key3 = make_key3(*set_ijk)
                    if key3 in mem3:
                        gcd2 = mem3[key3]
                    else:
                        key2 = make_key2(i, j)
                        if key2 not in mem2:
                            gcd1 = gcd(i, j)
                            mem2[key2] = gcd1
                        else:
                            gcd1 = mem2[key2]

                        key2 = make_key2(gcd1, k)
                        if key2 not in mem2:
                            gcd2 = gcd(gcd1, k)
                            mem2[key2] = gcd2
                        else:
                            gcd2 = mem2[key2]
                    ans += gcd2 * 6

    print(ans)

Submission status: Accepted

Solution code:
from math import gcd

k = int(input())

res = 0
mul = [0, 1, 3, 6]
for a in range(1, k+1):
    for b in range(a, k+1):
        for c in range(b, k+1):
            res += gcd(gcd(a, b), c) * mul[len({a, b, c})]

print(res)

Submission status: Accepted

Solution code:
import math
k=int(input())
sum=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):
   sum=sum+(math.gcd(a,l))
print(sum)

Submission status: Accepted

Solution code:
K=int(input())
s=0

import math
# 全部同じパターン
for i in range(1, K+1):
  # print("{} {} {}".format(i,i,i))
  s += i

# 2つ同じパターン
for i in range(1, K+1):
  for j in range(1,K+1):
    if i==j:
      continue
    # print("{} {} {}".format(i,i,j))
    s += math.gcd(i,j)*3

from itertools import combinations
# 全部違うパターン
for i in combinations(range(1,K+1), 3):
  # print("{} {} {}".format(i[0], i[1], i[2]))
  s += math.gcd(math.gcd(i[0], i[1]),i[2])*3*2

print(s)

Submission status: Accepted

Solution code:
import math

def f(a,b,c):
  return math.gcd(math.gcd(a,b),c)

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 += f(i,j,k)
print(ans)

Submission status: Accepted

Solution code:
k = int(input())
ans = [
    1,
    9,
    30,
    76,
    141,
    267,
    400,
    624,
    885,
    1249,
    1590,
    2208,
    2689,
    3411,
    4248,
    5248,
    6081,
    7485,
    8530,
    10248,
    11889,
    13687,
    15228,
    17988,
    20053,
    22569,
    25242,
    28588,
    31053,
    35463,
    38284,
    42540,
    46581,
    50893,
    55362,
    61824,
    65857,
    71247,
    76884,
    84388,
    89349,
    97881,
    103342,
    111528,
    120141,
    128047,
    134580,
    146316,
    154177,
    164817,
    174438,
    185836,
    194157,
    207927,
    218812,
    233268,
    245277,
    257857,
    268182,
    288216,
    299257,
    313635,
    330204,
    347836,
    362973,
    383709,
    397042,
    416448,
    434025,
    456967,
    471948,
    499740,
    515581,
    536073,
    559758,
    583960,
    604833,
    633651,
    652216,
    683712,
    709065,
    734233,
    754734,
    793188,
    818917,
    846603,
    874512,
    909496,
    933081,
    977145,
    1006126,
    1041504,
    1073385,
    1106467,
    1138536,
    1187112,
    1215145,
    1255101,
    1295142,
    1342852,
    1373253,
    1422195,
    1453816,
    1502376,
    1553361,
    1595437,
    1629570,
    1691292,
    1726717,
    1782111,
    1827492,
    1887772,
    1925853,
    1986837,
    2033674,
    2089776,
    2145333,
    2197483,
    2246640,
    2332104,
    2379085,
    2434833,
    2490534,
    2554600,
    2609625,
    2693919,
    2742052,
    2813988,
    2875245,
    2952085,
    3003306,
    3096024,
    3157249,
    3224511,
    3306240,
    3388576,
    3444609,
    3533637,
    3591322,
    3693924,
    3767085,
    3842623,
    3912324,
    4027884,
    4102093,
    4181949,
    4270422,
    4361548,
    4427853,
    4548003,
    4616104,
    4718640,
    4812789,
    4918561,
    5003286,
    5131848,
    5205481,
    5299011,
    5392008,
    5521384,
    5610705,
    5739009,
    5818390,
    5930196,
    6052893,
    6156139,
    6239472,
    6402720,
    6493681,
    6623853,
    6741078,
    6864016,
    6953457,
    7094451,
    7215016,
    7359936,
    7475145,
    7593865,
    7689630,
    7886244,
    7984165,
    8130747,
    8253888,
    8403448,
    8523897,
    8684853,
    8802826,
    8949612,
    9105537,
    9267595,
    9376656,
    9574704,
    9686065,
    9827097,
    9997134,
    10174780,
    10290813,
    10493367,
    10611772,
    10813692
]
print(ans[k-1])

Submission status: Accepted

Solution code:
K = int(input())

GCD = [[0]*200 for i in range(200)]
def gcd(x, y):
    if GCD[x-1][y-1] == 0:
        if y == 0:
            return x
        else:
            return gcd(y, x % y)
    else:
        return GCD[x-1][y-1]

tot = 0
for i in range(1, K+1):
    for j in range(1, K+1):
        s = gcd(i, j)
        if s != 1:
            for k in range(1, K+1):
                t = gcd(k, s)
                tot += t
        else:
            tot += K
print(tot)

Submission status: Accepted

Solution code:
import math
from functools import reduce

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

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):
            if 1 in [a,b,c]: ans += 1
            else: ans += gcd(a,b,c)

print(ans)

Submission status: Accepted

Solution code:
from math import gcd

n = int(input())
sum = 0
for i in range(1, n + 1):
    for j in range(1, i):
        for k in range(1, j):
            sum += 6 * gcd(gcd(k, j), i)
        sum += 6 * gcd(j, i)
    sum += i
print(sum)

Submission status: Accepted

Solution code:
from fractions import gcd
from functools import reduce

K = int(input())
tmp = [[0 for _ in range(K+1)] for _ in range(K+1)]
ans = 0
for a in (range(1, K+1)):
    for b in range(a, K+1):
        if tmp[a][b] != 0:
            gcd1 = tmp[a][b]
        else:
            gcd1 = gcd(a, b)
            tmp[a][b] = gcd1
        for c in range(b, K+1):
            n = 0
            if a == b == c:
                n = 1
            elif a == b or b == c or c == a:
                n = 3
            else:
                n = 6
            gcd2 = 0
            if tmp[gcd1][c] != 0:
                gcd2 = tmp[gcd1][c]
            else:
                gcd2 = gcd(gcd1, c)
                tmp[gcd1][c] = gcd2
            ans += n * gcd2
print(ans)