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:
import math
from functools import reduce
import time

K = int(input())

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

sum = 0

for a in range(1, K+1):
    for b in range(a, K+1):
        for c in range(b, K+1):
            G = gcd(a,b,c)
            if a == b and b == c:
                sum += G
            elif a == b or b == c:
                sum += G*3
            else:
                sum += G*6

print(sum)

Submission status: Accepted

Solution code:
import fractions

K = int(input())
ans = 0

for a in range(1,K+1):
    for b in range(a,K+1):
        t = fractions.gcd(a,b)
        for c in range(b,K+1):
            if(t!=1):
                tmp = fractions.gcd(t,c)
            else:
                tmp = 1
            if(a==b and b==c):
                ans += tmp
            elif(a!=b and b!=c and c!=a):
                ans += 6*tmp
            else:
                ans += 3*tmp
print(int(ans))

Submission status: Accepted

Solution code:
import math
n = int(input())
ans = 0
t = [math.gcd(i, j) for i in range(1, n+1) for j in range(1, n+1)]

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

print(ans)

Submission status: Accepted

Solution code:
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)
K = int(input())
t = 0
t1 = 0
t2 = 0
for i in range(1,K+1):
    for j in range(i,K+1):
        for l in range(j,K+1):
            if i == j == l:
                t = t + i
            elif i == j or j ==l or l ==i:
                t = t + 3 * gcd(i, j,l)
            else:
                t = t + 6 * gcd(i,j,l)
             
           
           
print(t)

Submission status: Accepted

Solution code:
import math

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

k = int(input())

s = 0
for i in range(1, k+1):
    if i == 1:
        s += k*k
        continue
    for j in range(1, k+1):
        if j == 1:
            s += k
            continue

        d = gcd(i, j)
        if d == 1:
            s += k
            continue

        for k in range(1, k+1):
            if k == 1:
                s += 1
                continue
            s += gcd(d, k)

print(s)

Submission status: Accepted

Solution code:
from fractions import gcd
from collections import defaultdict

n = int(input())
temp = defaultdict(int)
ans = 0

for i in range(1, n+1):
    for j in range(1, n+1):
      x = gcd(i,j)
      temp[x] += 1

for k,v in temp.items():
  for w in range(1, n+1):
    ans += gcd(k,w)* v

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
d = 0

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

for i in range(1,N+1):
  for j in range(i,N+1):
    for k in range(j,N+1):
      t = sorted((i,j,k))
      if i==j==k:
        n =1
      elif i==j or i==k or j ==k:
        n =3
      else:
        n =6
      d+= n*gcd(gcd(i,j),k)
print(d)

Submission status: Accepted

Solution code:
import math

k = int(input())

total = 0
for a in range(1,k+1):
    for b in range(a,k+1):
        for c in range(b,k+1):
            abc = {a,b,c}
            div = 1
            if len(abc) == 2:
                div = 3
            elif len(abc) == 1:
                div = 1
            elif len(abc) == 3:
                div = 6
            #print(str(a) + " " + str(b) + " " + str(c))
            add = div * math.gcd(math.gcd(a,b),c)
            #print(len(abc))
            #print(div)
            #print(add)
            total += add

print(total)

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

Solution code:
import math
from functools import reduce

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

K = int(input())
numberslist = []
sumgcd = 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 == k:
                sumgcd += gcd_list([i,j,k])
            elif i == j or j == k or k == i:
                sumgcd += gcd_list([i,j,k])*3
            else:
                sumgcd += gcd_list([i,j,k])*6
                 
print(sumgcd)

Submission status: Accepted

Solution code:
import math
import itertools 
import collections

K = int(input())
result = 0
for v in itertools.combinations_with_replacement(range(1,K+1), 3):
    a,b,c = v
    count = collections.Counter(v)
    if 3 in count.values():
        result += math.gcd(math.gcd(a,b), c)
    elif 2 in count.values():
        result += math.gcd(math.gcd(a,b), c)*3
    else:
        result += math.gcd(math.gcd(a,b), c)*6
print(result)

Submission status: Accepted

Solution code:
import math
from functools import reduce,lru_cache

K = int(input())

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

@lru_cache(maxsize=None)
def calc_temp_2(k):
    temp_2 = 0
    for j in range(1,k):
        for l in range(j+1,k):
            temp_2 += gcd(k, j, l) * 2
        temp_2 += gcd(k,j)
    return temp_2

@lru_cache(maxsize=None)
def dp(k):
    if k == 1:
        return 1
    else:
        temp_1 = sum([gcd(k, i) for i in range(1,k)])
        temp_2 = calc_temp_2(k)
        return dp(k-1) + k + temp_1 * 3 + temp_2 * 3

print(dp(K))

Submission status: Accepted

Solution code:
import math

# input
K = int(input())

# process
gcdl = []
for i in range(K):
    l = []
    for j in range(K):
        l.append(math.gcd(i+1, j+1))
    gcdl.append(l)
# print(gcdl)

ans = 0
for a in range(K):
    for b in range(a, K):
        for c in range(b, K):
            # print([a, b, c])
            if a == c:
                ans += a+1
            elif b == c:
                ans += gcdl[a][b]*3
            elif a == b:
                ans += gcdl[a][c]*3
            else:
                t = gcdl[a][b]
                t = gcdl[t-1][c]
                ans += t*6

# output
print(ans)

Submission status: Accepted

Solution code:
from functools import reduce
import itertools

def gcd_base(x,y):
    while y!=0:
        x,y = y,x%y
    return x

def gcd(num):
    return reduce(gcd_base,num)

ans = 0
k = int(input())
if k >=3:
    l = [i for i in range(1,k+1)]
    ll = list(itertools.combinations(l,3))
    for x in ll:
        ans += (gcd(x))*6
    ll = list(itertools.combinations(l,2))
    for x in ll:
        y = [x[0],x[0],x[1]]
        z = [x[0],x[1],x[1]]
        ans += (gcd(y))*3
        ans += (gcd(z))*3
    for i in l:
        tmp = [i,i,i]
        ans += gcd(tmp)
    print(ans)
elif k == 2:
    print(9)
elif k ==1:
    print(1)

Submission status: Accepted

Solution code:
import math
K = int(input())
Sum = 0
for i in range(K):
  for j in range(i + 1):
    x = math.gcd(i + 1, j + 1)
    for k in range(j + 1):
      y = math.gcd(j + 1, k + 1)
      if (i == j) and (i == k):
        Sum = Sum + math.gcd(x, y)
      elif (i == j) or (i == k) or (j == k):
        Sum = Sum + 3 * math.gcd(x, y)
      else:
        Sum = Sum + 6 * math.gcd(x, y)
print(Sum)

Submission status: Accepted

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

# table = np.zeros((K,K), dtype="int16")
table = [[0] * K for i in range(K)]

for a in range(K):
    for b in range(a, K):
        tmp = math.gcd(a+1, b+1)
        table[a][b] = tmp
        table[b][a] = tmp

res = 0
for a in range(K):
    for b in range(K):
        for c in range(K):
            res += table[table[a][b]-1][c]
print(res)

Submission status: Accepted

Solution code:
import numpy as np
from sklearn.utils.extmath import cartesian

k = int(input())
ls = [i for i in range(1, k+1)]
arr = cartesian([ls,ls,ls])

print(np.gcd(np.gcd(arr[:, 0], arr[:, 1]), arr[:, 2]).sum())

Submission status: Accepted

Solution code:
k = int(input())
def gcd(a, b, c):
    gcd1 = 1
    if a%c == 0 and b%c == 0:
        gcd1 = c
    elif a%2 == 0 and b%2 == 0 and c%2 == 0:
        gcd1 = 2
        for i in range(4, c//2+1, 2):
            if a%i == 0 and b%i == 0 and c%i == 0:
                gcd1 = i
    else:
        for i in range(3, c//2+1, 2):
            if a%i == 0 and b%i == 0 and c%i == 0:
                gcd1 = i
    # print(gcd1)
    return gcd1

sum_gcd = 0
for a in range(1, k+1):
    for b in range(1, a+1):
        for c in range(1, b+1):
            if a == b and b == c:
                sum_gcd += gcd(a, b, c)
            elif a == b or b == c or c == a:
                sum_gcd += 3*gcd(a, b, c)
            else:
                sum_gcd += 6*gcd(a, b, c)
print(sum_gcd)

Submission status: Accepted

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

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

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

    for j in range(1,i):
        for k in range(1,i):
            tmp = math.gcd(i,j)
            ret += 3*math.gcd(tmp,k)

print(ret)

Submission status: Accepted

Solution code:
import sys
import itertools
if sys.platform =='ios':
    sys.stdin=open('input_file.txt')

k=int(input())
l=[]
l.append([1, 1])
l.append([2 ,9])
l.append([3 ,30])
l.append([4 ,76])
l.append([5 ,141])
l.append([6 ,267])
l.append([7 ,400])
l.append([8 ,624])
l.append([9 ,885])
l.append([10, 1249])
l.append([11 ,1590])
l.append([12 ,2208])
l.append([13 ,2689])
l.append([14 ,3411])
l.append([15 ,4248])
l.append([16 ,5248])
l.append([17 ,6081])
l.append([18 ,7485])
l.append([19 ,8530])
l.append([20 ,10248])
l.append([21 ,11889])
l.append([22 ,13687])
l.append([23 ,15228])
l.append([24 ,17988])
l.append([25 ,20053])
l.append([26 ,22569])
l.append([27 ,25242])
l.append([28 ,28588])
l.append([29 ,31053])
l.append([30 ,35463])
l.append([31 ,38284])
l.append([32 ,42540])
l.append([33 ,46581])
l.append([34, 50893])
l.append([35 ,55362])
l.append([36 ,61824])
l.append([37 ,65857])
l.append([38 ,71247])
l.append([39 ,76884])
l.append([40 ,84388])
l.append([41 ,89349])
l.append([42 ,97881])
l.append([43 ,103342])
l.append([44 ,111528])
l.append([45 ,120141])
l.append([46 ,128047])
l.append([47 ,134580])
l.append([48 ,146316])
l.append([49 ,154177])
l.append([50 ,164817])
l.append([51 ,174438])
l.append([52 ,185836])
l.append([53 ,194157])
l.append([54 ,207927])
l.append([55 ,218812])
l.append([56 ,233268])
l.append([57 ,245277])
l.append([58 ,257857])
l.append([59 ,268182])
l.append([60 ,288216])
l.append([61 ,299257])
l.append([62 ,313635])
l.append([63 ,330204])
l.append([64 ,347836])
l.append([65 ,362973])
l.append([66 ,383709])
l.append([67 ,397042])
l.append([68 ,416448])
l.append([69 ,434025])
l.append([70 ,456967])
l.append([71 ,471948])
l.append([72 ,499740])
l.append([73 ,515581])
l.append([74 ,536073])
l.append([75 ,559758])
l.append([76 ,583960])
l.append([77 ,604833])
l.append([78 ,633651])
l.append([79 ,652216])
l.append([80 ,683712])
l.append([81 ,709065])
l.append([82 ,734233])
l.append([83 ,754734])
l.append([84 ,793188])
l.append([85 ,818917])
l.append([86 ,846603])
l.append([87 ,874512])
l.append([88 ,909496])
l.append([89 ,933081])
l.append([90 ,977145])
l.append([91 ,1006126])
l.append([92 ,1041504])
l.append([93 ,1073385])
l.append([94 ,1106467])
l.append([95 ,1138536])
l.append([96 ,1187112])
l.append([97 ,1215145])
l.append([98 ,1255101])
l.append([99 ,1295142])
l.append([100, 1342852])
l.append([101, 1373253])
l.append([102 ,1422195])
l.append([103 ,1453816])
l.append([104 ,1502376])
l.append([105 ,1553361])
l.append([106 ,1595437])
l.append([107 ,1629570])
l.append([108 ,1691292])
l.append([109 ,1726717])
l.append([110 ,1782111])
l.append([111 ,1827492])
l.append([112 ,1887772])
l.append([113 ,1925853])
l.append([114 ,1986837])
l.append([115 ,2033674])
l.append([116 ,2089776])
l.append([117 ,2145333])
l.append([118 ,2197483])
l.append([119 ,2246640])
l.append([120 ,2332104])
l.append([121 ,2379085])
l.append([122 ,2434833])
l.append([123 ,2490534])
l.append([124 ,2554600])
l.append([125 ,2609625])
l.append([126 ,2693919])
l.append([127 ,2742052])
l.append([128 ,2813988])
l.append([129 ,2875245])
l.append([130 ,2952085])
l.append([131 ,3003306])
l.append([132 ,3096024])
l.append([133 ,3157249])
l.append([134 ,3224511])
l.append([135 ,3306240])
l.append([136 ,3388576])
l.append([137 ,3444609])
l.append([138 ,3533637])
l.append([139 ,3591322])
l.append([140 ,3693924])
l.append([141 ,3767085])
l.append([142 ,3842623])
l.append([143,3912324])
l.append([144 ,4027884])
l.append([145 ,4102093])
l.append([146 ,4181949])
l.append([147 ,4270422])
l.append([148 ,4361548])
l.append([149 ,4427853])
l.append([150 ,4548003])
l.append([151 ,4616104])
l.append([152 ,4718640])
l.append([153 ,4812789])
l.append([154 ,4918561])
l.append([155 ,5003286])
l.append([156 ,5131848])
l.append([157 ,5205481])
l.append([158 ,5299011])
l.append([159 ,5392008])
l.append([160 ,5521384])
l.append([161 ,5610705])
l.append([162 ,5739009])
l.append([163 ,5818390])
l.append([164 ,5930196])
l.append([165 ,6052893])
l.append([166 ,6156139])
l.append([167 ,6239472])
l.append([168 ,6402720])
l.append([169 ,6493681])
l.append([170 ,6623853])
l.append([171 ,6741078])
l.append([172 ,6864016])
l.append([173 ,6953457])
l.append([174 ,7094451])
l.append([175 ,7215016])
l.append([176 ,7359936])
l.append([177 ,7475145])
l.append([178 ,7593865])
l.append([179 ,7689630])
l.append([180 ,7886244])
l.append([181 ,7984165])
l.append([182 ,8130747])
l.append([183 ,8253888])
l.append([184 ,8403448])
l.append([185 ,8523897])
l.append([186 ,8684853])
l.append([187 ,8802826])
l.append([188 ,8949612])
l.append([189 ,9105537])
l.append([190 ,9267595])
l.append([191 ,9376656])
l.append([192 ,9574704])
l.append([193 ,9686065])
l.append([194 ,9827097])
l.append([195 ,9997134])
l.append([196 ,10174780])
l.append([197 ,10290813])
l.append([198 ,10493367])
l.append([199 ,10611772])
l.append([200,10813692])
print(l[k-1][1])

Submission status: Accepted

Solution code:
import math

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

Submission status: Accepted

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

for i in range(1,k+1):
    for j in range(i,k+1):
        for l in range(j,k+1):
            if i==j and j==l:
                ans+=i
#                 print(i,j,l)
                
                
            elif i==j or j==l:
                ans+=3*math.gcd(i,l)
#                 print(i,j,l)
                
                
            else:
                ans+=6*math.gcd(math.gcd(i,j),l)
#                 print(i,j,l)
                
                
            
print(ans)

Submission status: Accepted

Solution code:
import math
from functools import reduce
ans = []
a = []

def gcd(*numbers):
    return reduce(math.gcd, numbers)
    
n = int(input())

for i in range(1, n+1):
    for j in range(1, n+1):
        ans.append(3*(math.gcd(i,j)))
        
for i in range(1,n+1):
    a.append(i)
mainas = sum(a)*2

for i in range(1, n-1):
    for j in range(i+1, n):
        for z in range(j+1, n+1):
            ans.append(6*(gcd(i,j,z)))
answer = sum(ans)-mainas
print(answer)

Submission status: Accepted

Solution code:
import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)

su = 0
N = int(input())
for i in range(1,N+1):
    for j in range(i+1,N+1):
        for k in range(j+1,N+1):
            su += gcd(i,j,k)
su *= 6
for x in range(1,N+1):
    for y in range(1,N+1):
        if x != y:
            su += 3*(gcd(x,y))
        else:
            su += x
print(su)

Submission status: Accepted

Solution code:
import math
k = int(input())
cnt = 0
for a in range(1, k+1):
    for b in range(a+1, k+1):
        for c in range(b+1, k+1):
            cnt += math.gcd(math.gcd(a, b), c) * 6

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

for i in range(1, k+1):
    cnt += i
print(cnt)

Submission status: Accepted

Solution code:
K = int(input())

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

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(gcd(a,b),c)

            
print(total)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from math import gcd
n = int(input())
res = 0
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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
k = int(input())
count=0
for p in range(1,k+1):
    for q in range(p,k+1):
        for r in range(q,k+1):
            if p == q == r:
                count+=math.gcd(math.gcd(p,q), r)
            elif p == q:
                count+=math.gcd(math.gcd(p,q), r)*3
            elif q == r:
                count+=math.gcd(math.gcd(p,q), r)*3
            elif p == r:
                count+=math.gcd(math.gcd(p,q), r)*3
            else:
                count+=math.gcd(math.gcd(p,q), r)*6
print(count)

Submission status: Accepted

Solution code:
k = int(input())

import math
ans = 0
ans1 = 0
ans2 = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        ans1 += math.gcd(i,j)

ans = ans + ans1*3

for i in range(1,k+1):
    for j in range(1,i):
        for l in range(1,j):
            ans2 += math.gcd(math.gcd(i,j),l)

ans += ans2*6
print(ans-sum(list(range(k+1)))*2)

Submission status: Accepted

Solution code:
import sys,math
import numpy as np

n=int(sys.stdin.readline())
#n,k=map(int,sys.stdin.readline().split())
#a=np.array(sys.stdin.readline().split(),dtype='int64')
#a=np.array([sys.stdin.readline().split() for i in range(n)],dtype='int64')
ans=0
for i in range(1,n+1):
    ans+=i
    if i!=n:
        for j in range(i+1,n+1):
            f=math.gcd(i,j)
            ans+=f*6
            if j!=n:
                for k in range(j+1,n+1):
                    ans+=math.gcd(f,k)*6

print(ans)

Submission status: Accepted

Solution code:
import math

K = int(input()) + 1
ans = 0
for a in range(1,K):
    for b in range(a,K):
        for c in range(b,K):
            ab = math.gcd(a,b)
            part = math.gcd(ab,c)
            if a == b or b == c:
                if not (a == b and b == c):
                    part = part * 3
            else:
                    part = part * 6                   
            ans += part
print(ans)

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
xlist = list(range(1,k+1))

for i in range(k+1):
    ans += i

if k > 1:
    for x in itertools.combinations(xlist, 2):
        ans += gcd(x[0], x[1]) * 6
        # print(x)
        
if k > 2:
    for x in itertools.combinations(xlist, 3):
        ans += gcd(x[0], x[1], x[2]) * 6
        # print(x)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
from functools import reduce

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

total=0
N=int(input())

for i in range(1,N+1):
    for j in range(i,N+1):
        if i==j:
            for k in range(j,N+1):
                if j==k:
                    total += gcd(i,j,k)
                else:
                    total += 3*gcd(i,j,k)
        else:
            for k in range(j,N+1):
                if j==k:
                    total += 3*gcd(i,j,k)
                else:
                    total += 6*gcd(i,j,k)
            
print(total)

Submission status: Accepted

Solution code:
k = int(input())
n = 3
mod = 10**9+7
dp = [0]*(k+1)
ans = 0
for i in range(1, k+1)[::-1]:
    res = pow(k//i, n, mod)
    for j in range(i*2, k+1, i):
        res-=dp[j]
    dp[i] = res%mod
    ans+=i*res
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:
import itertools as it
import math

K = int(input())

itr = range(1, K+1)
gcd_ = sum([math.gcd(math.gcd(i, j), k)
            for i, j, k in it.product(itr, itr, itr)])
print(gcd_)

Submission status: Accepted

Solution code:
import math
from collections import defaultdict
from functools import reduce

memo = defaultdict(int)


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


def gcd_with_memo(x, y):
    key = tuple(sorted([x, y]))
    if memo[key] != 0:
        value = memo[key]
    else:
        value = math.gcd(x, y)
        memo[key] = value
    return value


# def main():
#     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_with_memo(a, gcd_with_memo(b, c))
#     print(total)

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

    total = 0

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

    # print(total)

    # 2 kind
    for i in range(1, K + 1):
        for j in range(i + 1, K + 1):
            total += 6 * gcd(i, j)

    # print(total)

    # 3kind
    for i in range(1, K + 1):
        for j in range(i+1, K + 1):
            for k in range(j+1, K + 1):
                total += 6 * gcd(i, j, k)

    print(total)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
from functools import reduce

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 += reduce(math.gcd, [a, b, c])
print(ans)

Submission status: Accepted

Solution code:
import math
from functools import reduce

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

K=int(input())
gcd_sum=0
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            gcd_sum+=gcd(a,b,c)

print(gcd_sum)

Submission status: Accepted

Solution code:
import math

k = int(input())
A = 0

for a in range(1,k+1):
    for b in range(1,k+1):
        p = math.gcd(a,b)
        for c in range(1,k+1):
            y = math.gcd(p,c)
            A += y

print(A)

Submission status: Accepted

Solution code:
import math
K=int(input())
out=int(0)
if K<3:
    for i in range (1,K+1):
        for j in range (1,K+1):
            for k in range (1,K+1):
                out=out+math.gcd(math.gcd(i,j),k)
else:
    out = out + K*(K+1)/2
    for i in range (1,K):
        for j in range (i+1,K+1):
            out = out+6*math.gcd(i,j)

    for i in range (1,K-1):
        for j in range (i+1,K):
            for k in range (j+1,K+1):
                out=out+6*math.gcd(math.gcd(i,j),k)
print(int(out))

Submission status: Accepted

Solution code:
from math import gcd
from itertools import product
n = int(input())
def gcds(a,b,c):
  return gcd(gcd(a,b),c)
ans = 0
for i,j,k in product(range(1,n+1),repeat=3):
  ans += gcds(i,j,k)
print(ans)

Submission status: Accepted

Solution code:
import sys
import copy
import math
import bisect
import pprint
import bisect
from functools import reduce
from copy import deepcopy
from collections import deque
from decimal import *
 
import math
from functools import reduce
 
def gcd(*numbers):
    return reduce(math.gcd, numbers)
 
def gcd_list(numbers):
    return reduce(math.gcd, numbers)
if __name__ == '__main__':
    a = int(input())
 
    count = 0
 
    for i in range(1,a+1):
        for j in range(1, a + 1):
            for k in range(1, a + 1):
                count += gcd(i,j,k)
 
    print(count)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement
from math import gcd
K = int(input())
memo = {}
ans = 0
for a,b,c in combinations_with_replacement(range(1,K+1),3):
  v = gcd(a, gcd(b,c))
  n = len(set([a,b,c]))
  ans += v if n==1 else (3*v if n==2 else 6*v)
print(ans)

Submission status: Accepted

Solution code:
import math
from functools import reduce

K=int(input())

ans = 0

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

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

print(ans)

Submission status: Accepted

Solution code:
from math import gcd

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

Submission status: Accepted

Solution code:
import math

K = int(input())
ans = 0

for p in range(K):
    for q in range(K):
        for r in range(K):

            preans = 0
            preans = math.gcd((p+1),(q+1))
            ans += math.gcd(preans,(r+1))

print(ans)

Submission status: Accepted

Solution code:
import math
import itertools
from functools import reduce
k = int(input())
s = sum([reduce(math.gcd,t) for t in itertools.product(list(range(1,k+1)),repeat=3)])
print(s)

Submission status: Accepted

Solution code:
import math

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

Submission status: Accepted

Solution code:
import math
from functools import reduce
def gcd_list(numbers):
    return reduce(math.gcd, numbers)
K=int(input())
sum1=0
sum2=0
for i in range(1,K+1):
    c=i
    for j in range(c,K+1):
        b=j
        for k in range(b,K+1):
            a=k
            sum1 +=gcd_list([c,b,a])
def sigma(a):
    s=0
    for i in range(0,a+1):
        s+=i
    return(s)
for i in range(1,K+1):
    d=i
    for j in range(d,K+1):
        e=j
        sum2 +=gcd_list([d,e])
print(6*sum1+sigma(K)-6*sum2)

Submission status: Accepted

Solution code:
import math
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 += math.gcd(math.gcd(i,j),k)
  print(ans)
  
if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
from math import gcd
k = int(input())
tmp = 0

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

Submission status: Accepted

Solution code:
import math
def gcd(a,b,c):
    return math.gcd(math.gcd(a,b),c)
K=int(input())
sum=0
for a in range(1,K+1):
    for b in range(a,K+1):
        for c in range(b,K+1):
            if a==b==c: sum+=a
            elif a!=b!=c: sum+=gcd(a,b,c)*6 
            else: sum+=gcd(a,b,c)*3
print(sum)

Submission status: Accepted

Solution code:
import math
def resolve():
    K = int(input())
    D = []
    ans = 0
    for b in range(1, K + 1):
        for c in range(1, K + 1):
            D.append(math.gcd(b, c))

    for d in D:
        for a in range(1, K+1):
            ans += math.gcd(a, d)

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

s3=0
for a in range(3,k+1):
    for b in range(2,k):
        for c in range(1,k-1):
            if c<b<a:
                s3+=gcd(gcd(b,c),a)
s2 = 0
for a in range(2,k+1):
    for b in range(1,k):
        if b<a:
            s2+=gcd(a,b)
s = s3*6 + s2*6 +k*(k+1)/2
print(int(s))

Submission status: Accepted

Solution code:
import math
from functools import reduce
K=int(input())
def gcd(*numbers):
    return reduce(math.gcd, numbers)
ans = 0
for a in range(1, K+1):
    for b in range(1, a+1):
        for c in range(1, b+1):
            if a==b & b==c:
                ans += a
            elif a!=b & b!=c:
                ans += gcd(a,b,c)*6 
            else:
                ans += gcd(a,b,c)*3

print(ans)

Submission status: Accepted

Solution code:
from math import gcd
n=int(input())
answer = 0
a = []

for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            a.append(i)
            a.append(j)
            a.append(k)
            ans = a[0]
            for l in range(1,3):
                ans = gcd(ans, a[l])
            answer+=ans
            a=[]
print(answer)

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])