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 sys
import math

input = sys.stdin.readline

K = int(input())
ans = 0
for i in range(1, K + 1):
    for j in range(i, K + 1):
        n = math.gcd(i, j)
        for l in range(j, K + 1):
            if len(set([i, j, l])) == 1:
                ans += math.gcd(n, l)
            elif len(set([i, j, l])) == 2:
                ans += (math.gcd(n, l) * 3)
            else:
                ans += (math.gcd(n, l) * 6)

print(ans)

Submission status: Accepted

Solution code:
import math
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import math
K = int(input())
rep = 0
gcds = [[0 for i in range(201)] for _ in range(201)]
for a in range(1,K+1):
    for b in range(1,K+1):
        gcds[a][b] = math.gcd(a,b)
for a in range(1,K+1):
    for b in range(1, K+1):
        for c in range(1, K+1):
            rep += gcds[gcds[a][b]][c]
print(rep)

Submission status: Accepted

Solution code:
def gcd2(x, y):
    if y == 0:
        return x
    else:
        return gcd2(y, x % y)
def gcd3(x,y,z):
    return gcd2(gcd2(x, y), z)

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

print(ans)

Submission status: Accepted

Solution code:
def gcd(x,y):
    if memo[x][y] != 0:
        return memo[x][y]
    tmp_x = x
    tmp_y = y
    while y != 0:
        x,y = y,x%y
    memo[tmp_x][tmp_y] = x
    memo[tmp_y][tmp_x] = x
    return x

K = int(input())
ans = 0
memo = [[0]*(K+1) for _ in range(K+1)]

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

for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            ans += memo[memo[i][j]][k]

print(ans)

Submission status: Accepted

Solution code:
from math import gcd

K = int(input())

print(sum(gcd(gcd(a,b),c) for a in range(1,K+1)
          for b in range(1,K+1)
          for c in range(1,K+1)))

Submission status: Accepted

Solution code:
import math

def koyaku(a,b,c):
    totyu=math.gcd(a,b)
    return math.gcd(totyu,c)

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

print(ans)

Submission status: Accepted

Solution code:
#import re
#import heapq
#import bisect
#from collections import deque
import math
from functools import reduce

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

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

def gcd_list(numbers):
    return reduce(math.gcd, numbers)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    K = int(input())
    s = 0
    import math
    for i in range(1,K+1):
        for j in range(1,K+1):
            ij = math.gcd(i,j)
            if ij == 1:
                s += 1 * K
            else:
                for k in range(1,K+1):
                    s += math.gcd(ij,k)
    print(s)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    from fractions import gcd
    sys.setrecursionlimit(10 ** 6)
    input = sys.stdin.readline
    K = int(input())
    GCD = {}
    for a in range(1, K+1):
        for b in range(1, K+1):
            GCD[(a, b)] = gcd(a, b)
    ans = 0
    for a in range(1, K+1):
        for b in range(1, K+1):
            gcd_ = GCD[(a, b)]
            for c in range(1, K+1):
                ans += GCD[(gcd_, c)]
                
    print(ans)
    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import gcd
from itertools import combinations
N=int(input())
dif3=list(combinations(range(1,N+1), 3))
dif2=list(combinations(range(1,N+1),2))
res = 0
for i in dif3:
    a = gcd(i[0], i[1])
    res += 6 * gcd(a, i[2])
for i in dif2:
    res += 6 * gcd(i[0], i[1])
res += int(N*(N+1)/2)
print(res)

Submission status: Accepted

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

def gcd_3(a,b,c):
    x = math.gcd(a,b)
    y = math.gcd(x,c)
    return y
li = []
count = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        li.append(math.gcd(i,j))
for i in range(1,len(li)+1):
    for j in range(1,k+1):
        count += math.gcd(li[i-1],j)
print(count)

Submission status: Accepted

Solution code:
import heapq
import math
from collections import defaultdict
from itertools import permutations,combinations,combinations_with_replacement
from functools import reduce

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

K = int(input())
res = 0

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

print(res)

Submission status: Accepted

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

k = int(input())
s = 0
for i in range(1, k+1):
    for j in range(1, k+1):
        for k in range(1, k+1):
            s += reduce(math.gcd, [i, j, k])

print(s)

Submission status: Accepted

Solution code:
import math
K =int(input())
sum_num = 0
for i in range(K):
    for j in range(i+1):
        temp_gcd = math.gcd(i+1,j+1)
        if i != j:
            same = False
        else:
            same = True
        for k in range(j+1):
            temp_num = math.gcd(temp_gcd,k+1)
            if same:
                if i != k and j != k:
                    sum_num += temp_num * 3
                else:
                    sum_num += temp_num 
            else:
                if i != k and j != k:
                    sum_num += temp_num * 6
                else:
                    sum_num += temp_num * 3

                
                
print(sum_num)

Submission status: Accepted

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


# リスト l の最大公約数
def gcdlist(l):
    a = l[0]
    for i in range(len(l)):
        a = gcd(a, l[i])
    return a

K = int(input())

result = 0

for i in range(1, K + 1):
    for j in range(1, K + 1):
        for k in range(1, K + 1):
            l = [i, j, k]
            result += gcdlist(l)

print(result)

Submission status: Accepted

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

ans = 0
for a in range(K):
    for b in range(K):
        t = math.gcd(a+1,b+1)
        for c in range(K):
            ans += math.gcd(t,c+1)

print(ans)

Submission status: Accepted

Solution code:
K = int(input())

import math
from functools import reduce
import itertools


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

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

ans = 0

for a, b, c in itertools.combinations_with_replacement(range(1, K + 1), 3):
    if a == b == c:
        x = 1
    elif a == b or b == c or c == a:
        x = 3
    else:
        x = 6
    ans += gcd(a, b, c) * x

print(ans)

Submission status: Accepted

Solution code:
from  math import gcd
dic = {}
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 and b == c:
                sum_ += gcd(gcd(a, b),c)
            elif a == b or b == c or c == a:
                sum_ += gcd(gcd(a, b),c)*3
            else:
                sum_ += gcd(gcd(a, b),c)*6
print(sum_)

Submission status: Accepted

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

n=int(input())
ans=0
for i in range(1,n+1):
    for j in range(1,n+1):
        d=gcd(i,j)
        for k in range(1,n+1):
            ans+=gcd(d,k)
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())
ans = 0
for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            ans += gcd_list([a,b,c])

print(ans)

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

Solution code:
import math

K = int(input().strip())

ans = 0
for a in range(1,K+1):
    tmp = 0
    for b in range(1,K+1):
        for c in range(b + 1,K+1):
            tmp += math.gcd(a, math.gcd(b,c))
    tmp *= 2
    for b in range(1, K + 1):
        tmp += math.gcd(a, b)
    ans += tmp

print(ans)

Submission status: Accepted

Solution code:
# コードテストする
from fractions import gcd
K = int(input())
ans = 0
gcd_list = {}
for i in range(1, K+1):
    for j in range(1, K+1):
        gcd_list[i, j] = gcd(i, j)

for i in range(1, K+1):
    for j in range(1, K+1):
        hoge = gcd_list[(i, j)]
        for k in range(1, K+1):
            ans += gcd_list[(hoge, k)]
print(ans)

Submission status: Accepted

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

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

print(x)

Submission status: Accepted

Solution code:
import math
k = int(input())
ans = 0
# def gcd(a,b):
#     s = max(a,b)
#     gcd = 0
#     for p in range(1,s+1):
#         if a%p==0 and b%p == 0:
#             gcd = p
#     return gcd
for a in range(1,k+1):
    for b in range(1,k+1):
        gcdab = math.gcd(a,b)
        for c in range(1,k+1):
            # print(a,b,c,fractions.gcd(gcdab,c))
            ans += math.gcd(gcdab,c)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
K = int(input())
A = []
for i in range(K):
  for j in range(K):
    x = math.gcd(i+1,j+1)
    for k in range(K):
      A.append(math.gcd(x,k+1))
print(sum(A))

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(i+1, K+1):
        for k in range(j+1, K+1):
            cnt += gcd(i, j, k)


cnt *= 6


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

tmp = 0
for i in range(1, K+1):
    tmp += i
cnt += tmp
print(cnt)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
from functools import reduce

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

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

Submission status: Accepted

Solution code:
from math import gcd
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    k=II()
    ans=0
    for a in range(1,k+1):
        for b in range(1,k+1):
            g=gcd(a,b)
            for c in range(1,k+1):
                ans+=gcd(g,c)
    print(ans)

main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
from math import gcd
from functools import reduce

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

K = ii()
ans = 0

memo = dp3(-1, K+1, K+1, K+1)

for i in range(1, K+1):
    for j in range(i+1, K+1):
        for k in range(j+1, K+1):
            '''
            #l = sorted([i, j, k])
            l = [i, j, k]
            a, b, c = l[0], l[1], l[2]
            if memo[a][b][c] != -1:
                ans += memo[a][b][c]
            else:
                memo[a][b][c] = gcd_list(l)
                #memo[i][k][j] = memo[k][i][j] = memo[k][j][i] = memo[j][i][k] = memo[j][k][i] = memo[i][j][k]
                #memo[i][k][j] = memo[i][j][k]
                #memo[k][i][j] = memo[i][j][k]
                #memo[k][j][i] = memo[i][j][k]
                #memo[j][j][i] = memo[i][j][k]
                #memo[j][i][k] = memo[i][j][k]
                ans += memo[a][b][c]
                '''
            ans += gcd_list([i, j, k])*6

for i in range(1, K+1):
    for j in range(1, K+1):
        if i!=j:
            ans += gcd_list([i, i, j])*3

for i in range(1, K+1):
    ans += gcd_list([i, i, i])

print(ans)

Submission status: Accepted

Solution code:
import math


def solve(k):
    res = 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):
                res += math.gcd(c, d)
    return res


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


def test():
    assert solve(2) == 9
    assert solve(200) == 10813692


if __name__ == "__main__":
    # test()
    main()

Submission status: Accepted

Solution code:
import math
from functools import reduce

K = int(input())
sum = 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):
            sum += gcd(a, b, c)

print(sum)

Submission status: Accepted

Solution code:
from math import gcd
k=int(input())
L=[[0]*200 for i in range(200)]

for i in range(1,k+1):
    for j in range(1,k+1):
        L[i-1][j-1]=gcd(i,j)
        
r=0
for i in range(1,k+1):
    for j in range(1,k+1):
        for l in range(1,k+1):
            r+=L[L[i-1][j-1]-1][l-1]
print(r)

Submission status: Accepted

Solution code:
import itertools
import math
from functools import reduce
K = int(input())
n = list(range(1, K+1))
def gcd(numbers):
  return reduce(math.gcd, numbers)
ans = 0
for x in itertools.combinations_with_replacement(n, 3):
  if x[0] == x[1] == x[2]: ans += gcd(x)
  elif x[0] != x[1] and x[0] != x[2] and x[1] != x[2]:
    ans += gcd(x) * 6
  else: ans += gcd(x) * 3
print(ans)

Submission status: Accepted

Solution code:
import sys
IS = lambda: sys.stdin.readline().rstrip()
II = lambda: int(IS())
MII = lambda: list(map(int, IS().split()))

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

def main():
    k = II()
    sumv = 0
    # (a,a,a)
    for i in range(1, k+1):
        sumv += i
    # (a,a,b)
    for a in range(1, k):
        for b in range(a+1, k+1):
            sumv += 6*gcd(a, b)
    # (a,b,c)
    for a in range(1, k-1):
        for b in range(a+1, k):
            for c in range(b+1, k+1):
                sumv += 6*gcd(gcd(a, b), c)
    print(sumv)

if __name__ == '__main__':
    main()

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 k in range(j,K+1):
            if i==j and j==k:
                ans+= math.gcd(i,math.gcd(k,j))
            elif i==j or j==k:
                ans += 3*math.gcd(i,math.gcd(k,j))
            else:
                ans += 6*math.gcd(i,math.gcd(k,j))
print(ans)

Submission status: Accepted

Solution code:
s="0 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"
ss=s.split()
n=int(input())
print(ss[n])

Submission status: Accepted

Solution code:
import math

K = int(input())

ans = 0
arr = []

for b in range(1, K+1):
    for c in range(1, K+1):
        arr.append(math.gcd(b, c))

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

print(ans)

Submission status: Accepted

Solution code:
K = int(input())
import math
def gcd(a,b,c):
    return math.gcd(a,math.gcd(b,c))
s = 0
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(b+1,K+1):
            s = s + gcd(a,b,c)
t = 0
for a in range(1,K+1):
    for b in range(1,K+1):
        t = t + math.gcd(a,b)
print(s*2+t)

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

Solution code:
import math

K = int(input())
ans = 0
for i in range(K):
    for j in range(K):
        gcd_0 = math.gcd(i+1,j+1)
        if gcd_0 == 1:
            ans += gcd_0 * K
        else:
            for k in range(K):
                ans += math.gcd(gcd_0,k+1)

print(ans)

Submission status: Accepted

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

A = []
for i in range(K):
  for k in range(K):
    A.append(math.gcd(i+1,k+1))

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

print(ans)

Submission status: Accepted

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

ans = 0
for i in range(n):
    for j in range(n):
        if i > j:
            continue
        for k in range(n):
            if j > k:
                continue
            # print(i, j, k)
            g = math.gcd(i+1, math.gcd(j+1, k+1))
            # print(math.gcd(i+1, math.gcd(j+1, k+1)))
            if i != j and j != k:
                ans += g * 6
            elif i == j and j == k:
                ans += g
            else:
                ans += g * 3
            # ans += math.gcd(i+1, math.gcd(j+1, k+1))

print(ans)

Submission status: Accepted

Solution code:
import math

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

'''

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

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

print(ans)

Submission status: Accepted

Solution code:
from functools import lru_cache
import math

K = int(input())

M = [[math.gcd(i,j) for i in range(0, K+1)] for j in range(0,K+1)]
# @lru_cache(maxsize=4095)
# def gcd(a,b,c):
#     return math.gcd(math.gcd(a,b), c)
res = 0
for i in range(1, K+1):
    for j in range(1, K+1):
        for k in range(1, K+1):
            res += M[i][M[j][k]]
print(res)

Submission status: Accepted

Solution code:
import math

k = int(input())

res = 0

kkk = range(1,k + 1)

for i in kkk:
  for j in kkk:
    for t in kkk:
      ss1 = math.gcd(i, j)
      ss2 = math.gcd(ss1, t)
      res += ss2
print(res)

Submission status: Accepted

Solution code:
from math import gcd

K = int(input())

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

ans = 0
for i in range(1, K + 1):
  for j in range(1, K + 1):
    ij[i][j] = gcd(i, j)

for i in range(1, K + 1):
  for j in range(1, K + 1):
    for k in range(1, K + 1):
      ans += ij[ij[i][j]][k]

print(ans)

Submission status: Accepted

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

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

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

for i in range(1, K - 1):
    for j in range(i + 1, K):
        for k in range(j + 1, K + 1):
            x = math.gcd(i, j)
            c += math.gcd(x, k) * 6
ans = a + b + c
print(ans)

Submission status: Accepted

Solution code:
import math

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

Submission status: Accepted

Solution code:
import sys
import math

K=int(input())

my_gcd=dict()

for i in range(1,K+1):
    for j in range(i,K+1):
        g = math.gcd(i,j)
        
        p = i*300+j
        my_gcd[p]=g
        q = j*300+i
        my_gcd[q]=g

sum=0
for i in range(1,K+1):
    for j in range(1,K+1):
        g = my_gcd[i*300+j]
        for k in range(1,K+1):
            sum += my_gcd[g*300+k] 

print(sum)

Submission status: Accepted

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


S = 0

# all same
for i in range(1, N+1):
    S += i

# two is same
for i in range(1, N+1):
    for j in range(i+1, N+1):
        S += 6 * gcd(i, j)

# all not same
for i in range(1, N+1):
    for j in range(i+1, N+1):
        for k in range(j+1, N+1):
            S += 6 * gcd(gcd(i, j), k)

print(S)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
#import fractions

n = int(input())
#tmp = input().split()
#n,m,k = list(map(lambda a: int(a), tmp))

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

Submission status: Accepted

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

for a in range(1,k+1):
    for b in range(1,k+1):
        arfa = math.gcd(a,b)
        for c in range(1,k+1):
            ans += math.gcd(arfa,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())
ans = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            ans += gcd(a, b, c)
print(ans)

Submission status: Accepted

Solution code:
import math
K = int(input())
sumi = 0
for i in range(1,K+1):
    sumi += i
sumk = 0
for i in range(1,K+1):
    for k in range(1, K+1):
        if not i == k:
            sumk += math.gcd(i, k)
sumk *= 3
sumj = 0
for i in range(1, K+1):
    for k in range(i+1, K+1):
        for j in range(k+1, K+1):
            sumj += math.gcd(math.gcd(i, k),j)
sumj *= 6

print(sumi+sumk+sumj)

Submission status: Accepted

Solution code:
import math
import itertools

K = int(input())
a = list(range(1, K + 1))
it = itertools.product(a, repeat=2)

c = 0
for i, j in it:
    g = math.gcd(i, j)
    for j in a:
        c += math.gcd(g, j)

print(c)

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)
        if a == 1:
            ans += k
        else:
            for l in range(1,k+1):
                ans += math.gcd(a,l)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import math
from functools import reduce

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

def main():
    k = int(input())
    sum_ = 0

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

    print(sum_)

if __name__ == '__main__':
    main()

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):
    ans += a
for a in range(1,k):
    for b in range(a+1,k+1):
        ans += 6 * math.gcd(a,b)
for a in range(1,k-1):
    for b in range(a+1,k):
        for c in range(b+1,k+1):
            ans += 6 * gcd(a,b,c)
print(ans)

Submission status: Accepted

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

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

            if(i == 1 or j == 1):
                gcd1 = 1
            elif(i < j):
                gcd1 = GCD(j, i)
            else:
                gcd1 = GCD(i, j)
            for k in range(1, K+1):
                ans += GCD(gcd1, k)

    print(ans)



if __name__ == main():
    main()

Submission status: Accepted

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


# all of them are different
for i in range(1, K+1):
    ans += i
    for j in range(1, K+1):
        if i != j:
            ans += 3 * math.gcd(i, j)
    for j in range(i+1, K+1):
        for k in range(j+1, K+1):
            ans += 6 * math.gcd(math.gcd(i, j), k)
print(ans)

Submission status: Accepted

Solution code:
import math
K =int(input())
L = [0 for _ in range(K)]
for a in range(1,K+1):
  for b in range(1,K+1):
    L[math.gcd(a,b)-1] +=1
s = 0
for c in range(1,K+1):
    for k in range(K):
        for _ in range(L[k]):
            s += math.gcd(c,k+1)
print(s)

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 i in range(1, K-1):
    for j in range(i+1, K):
        for k in range(j+1, K+1):
            ans += gcd(i, j, k)*6
for i in range(1, K):
    for j in range(i+1, K+1):
        ans += math.gcd(i, j)*6
for i in range(1, K+1):
    ans += i
    
print(ans)

Submission status: Accepted

Solution code:
n=int(input())

import math

def gcd_(lis):
    ans=lis[0]
    for i in  lis[1:]:
        ans=math.gcd(ans,i)
    return ans

ans=0
for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            ans+=gcd_([i,j,k])
print(ans)

Submission status: Accepted

Solution code:
from math import gcd

K = int(input())
t = 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:
                t += a
            elif a == b:
                t += gcd(a,c)*3
            elif b == c:
                t += gcd(a,c)*3
            elif a == c:
                t += gcd(a,b)*3
            else:
                t += gcd(gcd(a,b), c) * 6
print(t)

Submission status: Accepted

Solution code:


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

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

    def gcd3(a, b, c):
        lst = [a, b, c]
        lst.sort()
        x, y, z = lst
        return gcd(gcd(x, y), z)

    ans = 0
    for a in range(1, k + 1):
        for b in range(1, k + 1):
            for c in range(1, k + 1):
                ans += gcd3(a, b, c)

    print(ans)


submit()

Submission status: Accepted

Solution code:
import fractions
import collections
d = collections.defaultdict(int)
n = int(input())
res = 0
for i in range(1, n + 1):
    for j in range(1, n + 1):
        #print(i, j)
        x = fractions.gcd(i, j)
        d[x] += 1
res = 0
#print(d)
for k in d:
    for i in range(1, n + 1):
        #print("gdc:", k, i , "=", fractions.gcd(k, i))
        x = fractions.gcd(k, i)
        res += x * d[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())
count  = 0
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            count += gcd(a,b,c)

print(count)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    from sys import stdin
    input = stdin.readline

    from math import gcd
    from collections import Counter
    import itertools

    k = int(input())
    gcd_table = [[1]*k for _ in range(k)]
    for i in range(k):
        for j in range(k):
            gcd_table[i][j] = gcd(i+1, j+1)

    c = Counter(list(itertools.chain.from_iterable(gcd_table)))

    count = 0
    for key, value in c.items():
        count += sum(gcd_table[key-1])*value
    print(count)

     
"""
    n = int(input())
    count = 0
    for i in range(1, n+1):
        if i%3!=0 and i%5!=0:
            count += i
    print(int(count))
"""

Submission status: Accepted

Solution code:
import math
kk = int(input())
s = 0
for i in range(1,kk+1):
    for j in range(i,kk+1):
        for k in range(j,kk+1):
            tmp = math.gcd((math.gcd(i,j)),k)
            if i==j:
                if j==k:
                    s += tmp
                else:
                    s += tmp*3
            elif j==k:
                s += tmp*3
            elif i==k:
                s += tmp*3
            else:
                s += tmp*6
print(s)