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:
from math import  gcd

k = int(input())
out = 0

# 3つとも同じ数字のとき
out = out + (1 + k) * k / 2

#2つが同じ数字の時
for i in range(k):
    a = i + 1
    b = i + 1
    for j in range(a - 1):
        c = j + 1
        out = out + gcd(a, c) * 6

#3つとも違うとき
for m in range(k):
    a = m + 1
    for n in range(a - 1):
        b = n + 1
        gcd2 = gcd(a, b)
        for o in range(b - 1):
            c = o + 1
            out = out + gcd(gcd2, c) * 6


print(int(out))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from math import gcd
import itertools

def calc(a,b,c):
    x=gcd(a,b)
    y=gcd(x,c)
    return y

n=int(input())
A=list(itertools.combinations_with_replacement(range(1,n+1), 3))

ans=0
for a,b,c in A:
    if a==b==c:
        ans+=calc(a,b,c)
    elif a!=b and a!=c and b!=c:
        ans+=calc(a,b,c)*6
    else:
        ans+=calc(a,b,c)*3
print(ans)

Submission status: Accepted

Solution code:
from math import gcd

N = int(input())
answer = 0
for a in range(1, N+1):
    for b in range(1, N+1):
        for c in range(1, N+1):
            answer += gcd(gcd(a, b), c)
print(answer)

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 a in range(1, K+1):
    for b in range(1, K+1):
        for c in range(1, K+1):
            _sum +=gcd(a, b, c)

print(_sum)

Submission status: Accepted

Solution code:
import math

n = int(input())
dic = {}

ans = 0
for i in range(1,n+1):
  for j in range(1,n+1):
    tmp1 = math.gcd(i,j)
    for k in range(1,n+1):      
      tmp = math.gcd(tmp1,k)
      
      ans += tmp
      
print(ans)

Submission status: Accepted

Solution code:
import math
from functools import reduce
K = int(input())
CNT= 0
def gcd(*numbers):
    return reduce(math.gcd, numbers)
for i in range(1,K+1):
    for j in range(1,K+1):
        GCD = gcd(i,j)
        if GCD == 1:
            CNT += K
        else:
            for k in range(1, K+1):
                if gcd(GCD,k) != 1:
                    CNT += gcd(GCD,k)
                else:
                    CNT += 1
print(CNT)

Submission status: Accepted

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

# def gcb(l):
#     gcb=0
#     for i in range(1,min(l)+1):
#         if sum([l[n]%i for n in range(len(l))])==0:
#             gcb=i
#     return gcb

s=0
#全て同じ
for a in range(K+1):
    s+=a
#二つ同じ：
for a in range(1,K+1):
    for b in range(a+1,K+1):
        s+=math.gcd(a,b)*6
#全て異なる
for a in range(1,K+1):
    for b in range(a+1,K+1):
        for c in range(b+1,K+1):
            s+=math.gcd(c,(math.gcd(a,b)))*6

print(s)

Submission status: Accepted

Solution code:
k = int(input())
l = [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(l[k-1])

Submission status: Accepted

Solution code:
def compute_gcm(x, y):
  if x == y:
    return x
  if x < y:
    s = x
    x = y
    y = s
  if x==1:
    return 1
  a = x%y
  if a == 0:
    return y
  return compute_gcm(y, a)

#print(compute_gcm(4,compute_gcm(2,2)))
k = int(input())
res = k**3-(k-1)**3
same1 = 0
same2 = 0
rate = [6,3,1]
for p in range(2,k+1):
  for q in range(p, k+1):
    same1 = int(p==q)
    gcm1 = compute_gcm(q,p)
    for r in range(q, k+1):
      same2 = int(q==r)
      gcm = compute_gcm(r,gcm1)
      res += gcm*rate[same1+same2]
      #print("p:{}, q:{}, r:{}, gcm:{}, rate:{}, sum:{}".format(p,q,r,gcm,rate[same1+same2],res))
print(res)

Submission status: Accepted

Solution code:
import sys
import fractions

def in_ctrl():
    _input = [_.rstrip() for _ in sys.stdin.readlines()]
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    K = int(_input[0])
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    return K


def out_ctrl(s):
    print(s)


if __name__ == "__main__":
    K = in_ctrl()
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    cnt = 0
    dict_ = {}
    for a in range(1,K+1):
        cnt += a
        for b in range(a+1,K+1):
            if '{}_{}'.format(a,b) in dict_:
                ans = dict_['{}_{}'.format(a,b)]
            else:
                ans = fractions.gcd(a,b)
                dict_['{}_{}'.format(a,b)] = ans
            cnt += 6*ans
            for c in range(b+1,K+1):
                if '{}_{}'.format(ans,c) in dict_:
                    _ans = dict_['{}_{}'.format(ans,c)]
                else:
                    _ans = fractions.gcd(ans, c)
                    dict_['{}_{}'.format(ans,c)] = _ans
                cnt += 6*_ans
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    out_ctrl(cnt)

Submission status: Accepted

Solution code:
import math

K = int(input())
S = 0

for i in range(1,K-1):
    for j in range(i+1,K):
        for k in range(j+1,K+1):
            S += math.gcd(i,math.gcd(j,k))

S *= 6

T = 0

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

T *= 6

U = (K*(K+1))//2

#print(S,T,U)
print(S+T+U)

Submission status: Accepted

Solution code:
import math
K = int(input())
ans = 0
for i in range(1,K+1):
    ans -= i*2
    for j in range(i,K+1):
        l = math.gcd(i,j)
        ans -= l*3
        for k in range(j,K+1):
            ans += math.gcd(l,k)*6

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
k=int(input())
s=[]
ans=0
for a in range(1,k):
  for b in range(a+1,k+1):
    s.append(math.gcd(a,b))
for c in range(1,k+1):
  for i in range(len(s)):
    ans+=math.gcd(s[i],c)*2
  for j in range(1,k+1):
    ans+=math.gcd(c,j)
print(ans)

Submission status: Accepted

Solution code:
import itertools

k = int(input())
arr = {i:{j:0 for j in range(k)} for i in range(k)}
def gcd(a, b):
    if a < b:
        a, b = b, a
    for i in range(1000):
        if a % b == 0:
            return b        
        b, a = a % b, b

ans = 0 
for a in range(k):
    for b in range(a, k):
        tmp = gcd(a + 1, b + 1)
        arr[a][b] = tmp
        arr[b][a] = tmp

for a in range(k):
    for b in range(a, k):
        tmp = arr[a][b]
        for c in range(k):
            if a != b:
                ans += arr[tmp - 1][c] * 2
            else:
                ans += arr[tmp - 1][c]
print(ans)

Submission status: Accepted

Solution code:
K = int(input())

def gcd(a, b): # 最大公約数
    a = abs(a)
    b = abs(b)
    while b:
        a, b = b, a % b
    return a # int
ans = 0
for i in range(1,K+1):
    for j in range(i,K+1):
        for k in range(j,K+1):
            d = gcd(gcd(i,j),k)
            if i==j==k:
                ans += d
            elif i==j or j== k or k==i:
                ans += 3*d
            else:
                ans += 6*d
print(ans)

Submission status: Accepted

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

ans1 = 0
ans2 = 0
ans3 = 0

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

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

for i in range(K):
    ans3+=i+1

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

        for k in range(1,K+1):
            ans += math.gcd(A,k)
print(ans)

Submission status: Accepted

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

K = int(input())
tmp = []

c = 0
for i in range(K):
    for j in range(K):
        tmp.append(math.gcd(i + 1, j + 1))
        c = c + 1

tmp2 = []
for k in tmp:
    for m in range(K):
        tmp2.append(math.gcd(k, m+1))

print(sum(tmp2))

Submission status: Accepted

Solution code:
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())
S = 0

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

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

for i in range(1,K+1):
    S+=i

print(S)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
k = int(input())
s = 0
i = 0
d = [0]*k*k
for a in range(1,k+1):
    for b in range(1,k+1):
        d[i] = math.gcd(a,b)
        i+=1
for c in range(1,k+1):
        s += sum(map(lambda x: math.gcd(x,c),d))
print(s)

Submission status: Accepted

Solution code:
def main():
    K = int(input())

    su = 0
    for a in range(1, K+1):
        for b in range(1, a+1):
            for c in range(1, b+1):
                tmp = dgcd(a, b, c)
                if a == b and b == c:
                    tmp *= 1
                elif a == b or b == c or a == c:
                    tmp *= 3
                else:
                    tmp *= 6

                su += tmp
    print(su)


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


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

k = int(input())
total = 0

#0こ
for i in range(1, k+1):
    total += i
#print(total)

#1こ,２こ
for i in range(1, k+1):
    for j in range(i+1, k+1):
        total += math.gcd(i, j) * 3 * 2
#print(total)

#3こ
for i in range(1, k+1):
    for j in range(i+1, k+1):
        for k in range(j+1, k+1):
            total += math.gcd(math.gcd(i, j), k) * 6
print(total)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
import math
from functools import reduce

def input():
    return sys.stdin.readline()

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

def resolve():
    k = int(input())



    sum_ans = 0
    for i in range(1, k+1):
        for j in range(1, k+1):
            for k in range(1, k+1):
                sum_ans += gcd(i, j, k)

    print(sum_ans)






if __name__ == "__main__":
    resolve()

Submission status: Accepted

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


K = int(input())

L = [[0] * (K+1) for _ in range(K+1)]
ans = 0

for a in range(1, K+1):
    for b in range(1, K+1):
        x, y = sorted([a, b])
        if L[x][y] == 0:
            d = gcd(a, b)
            L[x][y] = d
        else:
            d = L[x][y]
        for c in range(1, K+1):
            x, y = sorted([d, c])
            if L[x][y] == 0:
                t = gcd(d, c)
                L[x][y] = t
                ans += t
            else:
                ans += L[x][y]


print(ans)

Submission status: Accepted

Solution code:
import math
K = int(input())
l = []
for a in range(1, K+1):
    for b in range(1, K+1):
        l.append(math.gcd(a, b))
t = []
for x in l:
    for c in range(1, K+1):
        t.append(math.gcd(x, c))
print(sum(t))

Submission status: Accepted

Solution code:
import math
import itertools
from functools import reduce

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

K = int(input())

ans = 0
for lst in itertools.combinations_with_replacement([i + 1 for i in range(K)], 3):
    ans += int(6 / math.factorial(4 - len(set(lst)))) * gcd(list(lst))

print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd
n=int(input())
ans=0
for i in range(1,n+1):
  for k in range(i,n+1):
    gc=gcd(i,k)
    for _ in range(k,n+1):
      g=gcd(gc,_)
      if i==_:
        ans+=g
      elif i==k or k==_:
        ans+=g*3
      else:
        ans+=g*6
print(ans)

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 a in range(1,k+1):
    for b in range(1,k+1):
        if gcd(a,b) == 1:
            sum += 1 * k
            continue
        for c in range(1,k+1):
            sum += gcd(a,b,c)

print(sum)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
'''
import math
from functools import reduce

N = int(input())
s = 0

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

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

for i in range(1, N+1):
    for j in range(1, N+1):
        for k in range(1, N+1):
            s += gcd(i, j, k)


print(s)
'''

import math
from functools import reduce
import itertools


N = int(input())
s = 0

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

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

seq = list(range(1, N+1))
comb = list(itertools.combinations_with_replacement(seq,3))

#print(seq)
#print(comb)

i = 1
for c in comb:
    if i == 1 or (c[0] == c[1] and c[1] == c[2]):
        s += gcd(c[0], c[1], c[2])
    elif c[0] != c[1] and c[1] != c[2] and c[0] != c[2]:
        s = s + gcd(c[0], c[1], c[2]) * 6
    else:
        s = s + gcd(c[0], c[1], c[2]) * 3
    i += 1

print(s)

Submission status: Accepted

Solution code:
num = int(input())
def gcd(a,b,c):
    if(b > a):
        sub = b
        b = a
        a = sub
    while(a%b != 0):
        sub = b
        sub2 = a
        a = b
        b = sub2 % sub
    if(c > b):
        sub = c
        c = b
        b = sub
    while(b%c != 0):
        sub = c
        sub2 = b
        b = c
        c = sub2 % sub
    return(c)
sum = 0
for i in range(1,num + 1):
    for l in range(i,num + 1):
        for k in range(l,num + 1):
            if(i == l and l == k):
                sum += gcd(i,l,k)
            elif(i ==l or l == k or k == i):
                sum += 3 * gcd(i,l,k)
            else:
                sum += 6 * gcd(i,l,k)
print(sum)

Submission status: Accepted

Solution code:
import math

K = int(input())
SUM = 0
gcdlist = []
for i in range(1,K+1):
    for j in range(i,K+1):
        for k in range(j,K+1):
            gcd1 = math.gcd(i,j)
            gcd2 = math.gcd(gcd1,k)
            if i == j and j== k:
                SUM += gcd2
            elif i == j or j == k or k == i:
                SUM += gcd2*3
            else:
                SUM += gcd2*6

print(SUM)

Submission status: Accepted

Solution code:
import fractions
import itertools
k = int(input())

ans=k*(k+1)//2
for a in range(1,k+1):
    for b in range(a+1,k+1):
        t = fractions.gcd(a,b)
        for c in range(b,k+1):
            ans+=fractions.gcd(t,c)*6

print(ans)

Submission status: Accepted

Solution code:
from math import gcd


k = int(input())
answer = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            answer += gcd(gcd(a, b), c)
print(answer)

Submission status: Accepted

Solution code:
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(): # C163
    N = int(input())
    sum = 0
    for i in range(1, N+1):
        for j in range(1, N+1):
            for h in range(1, N+1):
                sum += gcd(i,j,h)
    print(sum)


main()

Submission status: Accepted

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

def gcd3(a, b, c):
    return math.gcd(math.gcd(a,b), c)
ans = 0

for i in range(1, K+1):
    for j in range(i+1, K+1):
        for k in range(j+1, K+1):
            ans += gcd3(i, j, k)

ans *= 6

for i in range(1, K+1):
    ans += gcd3(i, i, i)

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

Submission status: Accepted

Solution code:
# AtCoder Beginner Contest 162: C (2020/04/12)
import math
K = int(input())
S = 0
for a in range(1,K+1):
    for b in range(a,K+1):
        for c in range(b,K+1):
            x = [a, b, c]
            ans = x[0]
            for i in range(1, 3):
                ans = math.gcd(ans, x[i])
            if a == b and b == c:
                S = S + ans
            elif a == b or b == c:
                S = S + 3*ans
            else:
                S = S + 6*ans
print(S)

Submission status: Accepted

Solution code:

b=int(input())-1
ary=[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(ary[b])

Submission status: Accepted

Solution code:
K = int(input())

num_list = [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(num_list[K-1])

Submission status: Accepted

Solution code:
K=int(input())
ans=0
import math
from functools import reduce
 
def gcd(*numbers):
    return reduce(math.gcd, numbers)
 
def gcd_list(numbers):
    return reduce(math.gcd, numbers)
  
for a in range(K):
  for b in range(K):
    for c in range(K):
      ans+=gcd(a+1,b+1,c+1)
print(ans)

Submission status: Accepted

Solution code:
def find_gcd(x, y):
    while (y):
        x, y = y, x % y

    return x
s=int(input())
k=0
for i in range(1,s+1):
    for j in range(1, s + 1):
        for l in range(1, s + 1):
            k+=find_gcd(i,find_gcd(j,l))
print(k)

Submission status: Accepted

Solution code:
from fractions import gcd

K = int(input())
ans = (K * (K+1)) // 2

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

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

Submission status: Accepted

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

print( sum )

Submission status: Accepted

Solution code:
import math
n = int(input())
sum = 0
for i in range(1,n+1):
    for j in range(i+1,n+1):
        for k in range(j+1,n+1):
            sum += math.gcd(math.gcd(k,j), i)
sum = sum * 6
sum_2 = 0
for i in range(1,n+1):
    for j in range(i+1,n+1):
         sum_2 += math.gcd(i,j)
     
sum_2= sum_2*3*2
sum_3 = n*(n+1)/2

sum= sum + sum_2+ sum_3
print(int(sum))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import fractions
gcd_map = [[0 for i in range(401)] for i in range(401)]


def mem_gcd(p, q):
    if gcd_map[p][q] == 0:
        gcd_map[p][q] = fractions.gcd(p, q)
    return gcd_map[p][q]


k = int(input())
res = 0
for a in range(1, k+1):
    for b in range(a, k+1):
        tmp_gcd = mem_gcd(a, b)
        for c in range(b, k+1):
            tk = mem_gcd(tmp_gcd, c)
            if a == b:
                if b == c:
                    res += tk
                else:
                    res += tk * 3
            else:
                if b == c:
                    res += tk*3
                else:
                    res += tk*6

print(res)

Submission status: Accepted

Solution code:
from math import gcd

k = int(input())
answer = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            answer += gcd(gcd(a, b), c)
print(answer)

Submission status: Accepted

Solution code:
import math
import itertools

K = int(input()) + 1
L = list(itertools.combinations_with_replacement(list(range(1, K)), 3))
a = 1
A = 0
for i in L:
  if len(set(i)) == 3:
    a = 6
  elif len(set(i)) == 2:
    a = 3
  else:
    a = 1
  A += math.gcd(math.gcd(i[0], i[1]), i[2]) * a
print(A)

Submission status: Accepted

Solution code:
n = int ( input() )

def find_gcd(x, y): 
      
    while(y): 
        x, y = y, x % y 
      
    return x 

dicts = {}
total = 0 
storedict = {}
for i in range(1, n + 1):
    for j in range(1, n + 1):
        
        strin = str(i) + "," + str(j)
        if strin not in dicts:
            gh = find_gcd(i, j)
            strin3 = str(j) + "," + str(i)
            dicts[strin] = gh 
            dicts[strin3] = gh 
            
        else:
            gh = dicts[strin]
        
        if gh not in storedict:
            storedict[gh] = 1 
        else:
            storedict[gh] += 1 

for k in range( 1 , n + 1):
    for key, value in storedict.items():
        gh = find_gcd(key, k)
        
        strin2 = str(gh) + "," + str(k)
        
        if strin2 not in dicts:
            gh = find_gcd(gh, k)
            strin4 = str(k) + "," + str(gh)
            dicts[strin2] = gh 
            dicts[strin4] = gh 
        else:
            gh = dicts[strin2]
            
        ans1 = gh * value    
        total += ans1 
print(total)

Submission status: Accepted

Solution code:
import math
from functools import reduce

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

k = int(input())
tmp = 0
for a in range(1, k+1):
  for b in range(a, k+1):
    for c in range(b, k+1):
      #print('a='+str(a)+', b='+str(b)+', c='+str(c))
      if a == b and a == c:
        tmp += gcd_list([a, b, c]) 
      elif a == b and a != c:
        tmp += gcd_list([a, b, c]) * 3
#        tmp += gcd_list([b, c, a]) 
#        tmp += gcd_list([c, a, b]) 
      elif b == c and a != c:
        tmp += gcd_list([a, b, c]) * 3
#        tmp += gcd_list([b, c, a]) 
#        tmp += gcd_list([c, a, b]) 
      elif a == c and b != c:
        tmp += gcd_list([a, b, c]) * 3
#        tmp += gcd_list([b, c, a]) 
#        tmp += gcd_list([c, a, b]) 
      else:
        tmp += gcd_list([a, b, c]) * 6
#        tmp += gcd_list([a, c, b])
#        tmp += gcd_list([b, a, c])
#        tmp += gcd_list([b, c, a])
#        tmp += gcd_list([c, a, b])
#        tmp += gcd_list([c, b, a])
print(tmp)

Submission status: Accepted

Solution code:
# coding: utf-8
 
N  = int(input())
sum = 0
 
import math
from functools import reduce
 
def gcd(*numbers):
    return reduce(math.gcd, numbers)
 
for i in range (N):
    for j in range(N):
        for k in range(N):
            sum += gcd(*[i+1, j+1, k+1])
 
print(sum)

Submission status: Accepted

Solution code:
from math import gcd
from functools import reduce


def gcd_kai(*numbers):
    return reduce(gcd, numbers)


K = int(input())
ans = 1
if K == 1:
    next
else:
    ans += (K - 1) * K * 3
    ans_sub = 0
    for i in range(2, K):
        for j in range(i + 1, K + 1):
            for k in range(i, K + 1):
                ans_sub += gcd_kai(i, j, k)
    ans += ans_sub * 3
    for i in range(2, K + 1):
        ans += i
print(ans)

Submission status: Accepted

Solution code:
import math
k=int(input())


sum=k*(k+1)/2

for l in range(1,k):
  for m in range(l+1,k+1):
    sum=sum+6*math.gcd(l,m)


for l in range(1,k-1):
  for m in range(l+1,k):
    for n in range(m+1,k+1):
      sum=sum+6*math.gcd(l,math.gcd(m,n))
      
print(int(sum))

Submission status: Accepted

Solution code:
k = int(input())
from fractions import gcd
from functools import reduce

x = 3*k*k - 3*k +1
for a in range(2, k+1):
  for b in range(a, k+1):
    if gcd(a,b)==1:
      x += 6*(k-b)+3
    else:
      for c in range(b, k+1):
        if len({a, b, c})==1:
          x += reduce(gcd, [a,b,c])
        elif len({a, b, c})==2:
          x += 3*reduce(gcd, [a,b,c])
        else:
          x += 6*reduce(gcd, [a,b,c])
      
print(x)

Submission status: Accepted

Solution code:
k = int(input())
gdc_table = [[-1 for _ in range(k+1)] for _ in range(k+1)]

def gdc(a, b):
	if a < b:
		a, b = b, a

	if b == 0:
		gdc_table[a][b] = a
	else:
		if gdc_table[a][b] == -1:
			gdc_table[a][b] = gdc(b, a%b)
	return gdc_table[a][b]

for i in range(0, k+1):
	for j in range(0, i+1):
		gdc_table[i][j] = gdc(i, j)
		gdc_table[j][i] = gdc_table[i][j]

# def gdc(a, b):
# 	if a < b:
# 		a, b = b, a
# 	init_a, init_b = a, b
# 	if gdc_table[init_a][init_b] == -1:
# 		while b:
# 			a, b = b, a % b
# 	# return a	
# 		gdc_table[init_a][init_b] = a
# 	return gdc_table[init_a][init_b]

# def triple_gdc(a, b, c):
# 	return gdc(gdc(a, b), c)

ans= 0
for first in range(1, k+1):
	for second in range(1, k+1):
		gdc1 = gdc_table[first][second]
		for third in range(1, k+1):
			# if gdc_table[gdc1][third] == -1:
			# 	print("Alert!")
			# 	print("gdc1", gdc1)
			# 	print("third", third)
			# 	break
			ans += gdc_table[gdc1][third]

print(ans)
# print("gdc_table[198]", gdc_table[198])

Submission status: Accepted

Solution code:
from math import gcd
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):
            s=len(set([i,j,k]))
            if s==1:
                p=1
            elif s==2:
                p=3
            elif s==3:
                p=6
            tmp=gcd(i,j)
            tmp= p*gcd(tmp,k)
            ans+=tmp
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
e=0
N=int(input())
c=np.arange(1, N+1)
for i in range(N):
 a=np.array([(i+1)]*N)
 for j in range(N):
  b=np.array([(j+1)]*N)
  d=np.gcd.reduce([a, b, c])
  e+=np.sum(d)
print(e)

Submission status: Accepted

Solution code:
import numpy as np
from numba import jit


@jit
def gcd(K):
    ans = 0

    for x in range(1, K + 1):
        for y in range(1, K + 1):
            for z in range(1, K + 1):
                ans += np.gcd(np.gcd(x, y), z)

    return ans


def main():
    K = int(input())

    print(gcd(K))


if __name__ == "__main__":
    main()