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

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

a = int(input())

ans = 0

for i in range(1,a+1):
    for j in range(1,i+1):
        for k in range(1,j+1):
            if i == j and i == k:
                ans += gcd(i,j,k)
            elif i == j or i == k or j == k:
                ans += gcd(i,j,k)*3
            else:
                ans += gcd(i,j,k)*6

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from functools import reduce
def input(): return sys.stdin.readline().rstrip()
def gcd(*numbers):
    return reduce(math.gcd, numbers)
def main():
    k=int(input())
    sum=0
    for i in range(1,k-1):
        for j in range(i+1,k):
            for l in range(j+1,k+1):
                sum+=gcd(i,j,l)*6
    for i in range(1,k+1):
        for j in range(1,k+1):
            if i!=j:
                sum+=gcd(i,j,j)*3
    for i in range(1,k+1):
        sum+=gcd(i,i,i)
    print(sum)

if __name__=='__main__':
    main()

Submission status: Accepted

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

for i in range(n):
    num1 = i + 1
    for j in range(n - num1 + 1):
        num2 = j + num1
        gcd1 = math.gcd(num1, num2)
        for k in range(n - num2 + 1):
            num3 = k + num2
            gcd2 = math.gcd(gcd1, num3)
            if num1 == num2 and num2 == num3:
                ans += gcd2
            elif num1 == num2 or num2 == num3:
                ans += gcd2 * 3
            else:
                ans += gcd2 * 6

print(ans)

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)

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

print(count)

Submission status: Accepted

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

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


main()

Submission status: Accepted

Solution code:
import math

K = int(input())
r = 0

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

print(r)

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

Submission status: Accepted

Solution code:
import math

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

print(ans)

Submission status: Accepted

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

gcdmem = [[[0] * (K+1) for i in range(K+1)] for j in range(K+1)]

for a in range(1, K+1):
    for b in range(a, K+1):
        for c in range(b, K+1):
            if gcdmem[a][b][c] > 0:
                continue
            gcdab = math.gcd(a, b)
            gcdmem[a][b][c] = math.gcd(gcdab, c)

ans = 0
for a in range(1, K+1):
    for b in range(1, K+1):
        for c in range(1, K+1):
            s1, s2, s3 = sorted([a, b, c])
            ans += gcdmem[s1][s2][s3]

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math


K = int(input())
ans = 0
ab = []
for a in range(1, K+1):
    for b in range(1, K+1):
        g = math.gcd(a, b)
        for c in range(1, K+1):
            ans += math.gcd(c, g)
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 n in range(1, k + 1):
            tmp = math.gcd(i, j)
            cnt += math.gcd(tmp, n)
print(cnt)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from math import gcd
def main():
    k = int(input())
    t = [0]*201
    for i in range(1, k+1):
        for j in range(1, k+1):
            t[gcd(i, j)] += 1
    ans = 0
    for i in range(1, 201):
        if t[i] > 0:
            for j in range(1, k+1):
                x = gcd(i, j)
#                print(x)
                ans += x*t[i]
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
from sys import stdin
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)
    
#A, B, C = [int(x) for x in stdin.readline().rstrip().split()]
K = int(input())

counter = 0

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

print(counter)

Submission status: Accepted

Solution code:
from math import gcd

n = int(input())

sum = 0

for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1, n+1):
            sum += gcd(gcd(i,j),k)

print(sum)

Submission status: Accepted

Solution code:
from math import gcd

K = int(input())

s = 0

for a in range(1, K+1):
    for b in range(1, K+1):
        d = gcd(a, b)
        if d == 1:
            s += K
            continue
        else:
            for c in range(1, K+1):
                s += gcd(d, c)

print(s)

Submission status: Accepted

Solution code:
from math import gcd
def main():
    K = int(input())
    r = 0
    l = {}
    for i in range(1, K+1):
        for j in range(1, K+1):
            for k in range(1, K+1):
                x = gcd(i,j)
                x = gcd(x,k)
                r += x
    return r
print(main())

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(K: int):
    s = 0
    for i in range(1, K + 1):
        for j in range(1, K + 1):
            g1 = gcd(i, j)
            for k in range(1, K + 1):
                g2 = gcd(g1, k)
                s += g2
    print(s)
    return


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
    # m = min(a, b)
    # g = 1
    # for i in range(1, m+1):
    #    if a % i == 0 and b % i == 0:
    #        g = i 
    # return g


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  # type: int
    solve(K)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

summation = 0

K = int(input())
for i in range(1, K + 1):
    for j in range(1, K + 1):
        gcd_i_j = math.gcd(i, j)
        for k in range(1, K + 1):
            gcd = math.gcd(gcd_i_j, k)
            summation += gcd

print(summation)

Submission status: Accepted

Solution code:
import math

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


K = int(input())

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from math import gcd

def solve(K: int):
    sum = 0
    #1つしか数字がない時
    for i1 in range(1,K+1):
        sum+=i1
        # print(f"i1:{i1}")
    #2つ数字がある時
    for i2 in range(1,K+1):
        for j2 in range(i2+1,K+1):
            sum+=6*gcd(i2,j2)
            # print(f"i2:{i2},j2:{j2}")
    #3つ数字がある時
    for i in range(1,K+1):
        for j in range(i+1,K+1):
            for k in range(j+1,K+1):
                sum+=6*gcd(gcd(i,j),k)
    print(sum)


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  # type: int
    solve(K)

if __name__ == '__main__':
    main()

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import functools
import math

k = int(input())
cnt = 0


def gcd(a, b, c):
    return functools.reduce(math.gcd, [a, b, c])


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

print(cnt)

Submission status: Accepted

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

lsgcd=[]

for i in range(1,k+1):
    for j in range(1, k +1):
        lsgcd.append(math.gcd(i,j))


ls2 = []
for i in lsgcd:
    for j in range(1,k+1):
        ls2.append(math.gcd(i,j))

print(sum(ls2))

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# ABC162_C
from math import gcd
k=int(input())
t=[]
for i in range(1,k+1):
    for j in range(1,k+1):
        t.append(gcd(i,j))
ans=[]
for tt in t:
    for i in range(1,k+1):
        ans.append(gcd(tt,i))
print(sum(ans))

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

Solution code:
import math
from functools import reduce

def main():
    k = int(input())
    ans = 0
    ary = []
    for i in range(1,k+1):
        for j in range(1,k+1):
            ary.append(math.gcd(i,j))
    for i, aa in enumerate(ary):
        for j in range(1,k+1):
            ans += math.gcd(aa,j)
    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:
import math
from functools import reduce
K = int(input())


# gcd
def gcd_base(x, y):
    return math.gcd(x, y)


# 3つ以上
def gcd_list(numbers):
    return reduce(gcd_base, numbers)


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:
import math
a=int(input())
counter=0
for i in range(1,a+1):
    for j in range(1,a+1):
        tmp=math.gcd(i,j)
        for k in range(1,a+1):
            counter+=math.gcd(tmp,k)
print(counter)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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(a, k+1):
        for c in range(b, k+1):
            if a==b and b==c:
                ans += gcd_list([a, b, c])
            elif a!=b and b!=c:
                ans += gcd_list([a, b, c]) * 6
            else:
                ans += gcd_list([a, b, c]) * 3
print(ans)

Submission status: Accepted

Solution code:
from math import gcd
k = int(input())
res = [0]*201
for i in range(1,k+1):
    for j in range(1,k+1):
        res[gcd(i,j)]+=1
ans = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        ans += gcd(i,j)*res[i]

print(ans)

Submission status: Accepted

Solution code:
import math
import itertools

from sys import stdin
import sys
sys.setrecursionlimit(10**8)

def nextLine(): return next(stdin)
def nextStrList(): return nextLine().split()
def nextIntList(): return [int(_) for _ in nextStrList()]

# def main0():
# # 	k=int(nextLine())
# 	k=200
# 	s=0
# 	for a,b,c in itertools.product(range(1,k+1), repeat=3):
# 		g=math.gcd(math.gcd(a,b),c)
# 		s+=g
# 	print(s)
	
	
def main():
	k=int(nextLine())
# 	k=200
	s=0
	for a,b,c in itertools.combinations(range(1,k+1), 3):
		g=math.gcd(math.gcd(a,b),c)
		g*=6
		s+=g
	for a,b in itertools.combinations(range(1,k+1), 2):
		g=math.gcd(a,b)
		g*=6
		s+=g
	for a in range(1,k+1):
		g=a
		s+=g
	print(s)
	
	
if __name__=="__main__":
# 	main0()
	main()

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

Submission status: Accepted

Solution code:
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]

from math import gcd
n=n0()
s=0
for a in range(1,n+1):
    for b in range(a,n+1):
        for c in range(b,n+1):
            if a==b==c:
                s+=gcd(gcd(a,b),c)
            elif a==b or b==c:
                s+=3*gcd(gcd(a,b),c)
            else:
                s+=6*gcd(gcd(a,b),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(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:
from math import gcd
n = int(input())
ans = 0
for i in range(1, n+1):
    for j in range(1, n+1):
        t = gcd(i, j)
        if t == 1:
            ans += n
        else:
            for k in range(1, n+1):
                ans += gcd(t, k)
print(ans)

Submission status: Accepted

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

K=int(input())
ans=0
memo=[[[-1 for i in range(K+1)] for j in range(K+1)] for k in range(K+1)]

for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            if memo[i][j][k]==-1:
                v=gcd(i,gcd(j,k))
                memo[i][j][k]=v
                memo[i][k][j]=v
                memo[j][k][i]=v
                memo[j][i][k]=v
                memo[k][i][j]=v
                memo[k][j][i]=v
            else:
                v=memo[i][j][k]
            ans+=v

print(ans)

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(1,K+1):
    for h in range(1,K+1):
      x = gcd(i,j)
      y = gcd(x,h)
      ans += y
print(ans)

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())
answer = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for h in range(1,K+1):
            answer += gcd(i,j,h)
print(answer)

Submission status: Accepted

Solution code:
from fractions import gcd

k = int(input())
s = 0
mem = {}
for a in range(1, k + 1):
    for b in range(1, k + 1):
        if mem.get((a, b)) is None:
            g = gcd(a, b)
            mem[(a, b)] = g
            mem[(b, a)] = g
        else:
            g = mem[(a,b)]            
        for c in range(1, k + 1):
            if mem.get((g, c)) is None:
                h = gcd(g, c)
                mem[(g, c)] = h
                mem[(c, g)] = h
                s += h
            else:
                s += mem[(g, c)]
print(s)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement, permutations

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

def main():
    K = int(input())
    ans = 0
    for i in range(K):
        for j in range(K):
            for k in range(K):
                temp = gcd(i+1, j+1)
                temp = gcd(temp, k+1)
                ans += temp
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
x = int(input())
ans = 0
memo = {}
for i in range(1, x+1):
    for j in range(1, x+1):
        a,b = min(i,j), max(i,j)
        if (a,b) in memo.keys():
            l = memo[(a,b)]
        else:
            l = math.gcd(a,b)
            memo[(a,b)] = l
        for k in range(1, x+1):
            ans += math.gcd(l,k)
print(ans)

Submission status: Accepted

Solution code:
import math

k = int(input())

ans = 0
for a in range(1, k + 1):
    for b in range(1, k + 1):
        _gcd = math.gcd(a, b)

        if _gcd == 1:
            ans += k
        else:
            for c in range(1, k + 1):
                ans += math.gcd(_gcd, c)

print(ans)

Submission status: Accepted

Solution code:
from math import gcd
from functools import reduce


def gcd_lst(numbers):
    return reduce(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_lst([a, b, c])
print(ans)

Submission status: Accepted

Solution code:
#MLE注意！

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    k = int(input())
    def gcd(a, b):
        if b == 0:
            return a
        else:
            return gcd(b, a % b)
    
    def gcd_group(arr):
        g = gcd(arr[0], arr[1])
        for i in range(2, len(arr)):
            g = gcd(g, arr[i])
        return g
    
    def lcm(a, b):
        g = gcd(a, b)
        return (a*b)//g
    
    def lcm_group(arr):
        l = lcm(arr[0], arr[1])
        for i in range(2, len(arr)):
            l = lcm(l, arr[i])
        return l
    
    res = 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:
                    res += gcd_group([a,b,c]) 
                elif a==b or b==c or a==c:
                    res += gcd_group([a,b,c]) * 3
                else:
                    res += gcd_group([a,b,c]) * 6
    print(res)

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

Submission status: Accepted

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

ans = 0

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

Submission status: Accepted

Solution code:
import math

K = int(input())

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

gcd_count = [0] * 201

for a in range(1,K + 1):
    for b in range(1,K + 1):
        gcd_count[table[a][b]] += 1

ans = 0

for ab in range(1,K + 1):
    for c in range(1,K + 1):
        ans += gcd_count[ab] * table[ab][c]

print(ans)

Submission status: Accepted

Solution code:
import math

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

Submission status: Accepted

Solution code:
k = int(input())

memo = [[-1 for _ in range(k+1)] for _ in range(k+1)]


def gcd(a, b):
    if -1 != memo[a][b]:
        return memo[a][b]
    r = a % b
    if r == 0:
        memo[a][b] = b
        return b
    else:
        ans = gcd(b, r)
        memo[a][b] = ans
        return ans


def gcd_m(a, b, c):
    lst = sorted([a, b, c], reverse=True)
    return gcd(gcd(lst[0], lst[1]), lst[2])


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_m(a, b, c)
print(ans)

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

Submission status: Accepted

Solution code:
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

K = int(input())

cnt = 0
for i in range(1, K+1):
    for j in range(1, K+1):
        for k in range(j+1, K+1):
            cnt += 2 * gcd(i, gcd(j, k))
    for j in range(1, K+1):
        cnt += gcd(i, gcd(j, j))
print(cnt)

Submission status: Accepted

Solution code:
import math
from functools import reduce

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

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

    sum_count = 0
    for i in range(1,n+1):
        tmp_list = []
        tmp_list.append(i)
        for j in range(1,n+1):
            tmp_list.append(j)
            for k in range(1,n+1):
                tmp_list.append(k)              
                sum_count += gcd_list(tmp_list)
                tmp_list.pop(2)
            tmp_list.pop(1)

    print(sum_count)        

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

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

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

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
#from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]
debugmode = False

k = INT()
ans = 0
for a in range(1, k + 1):
    for b in range(a, k + 1):
        for c in range(b, k + 1):
            g = gcd(gcd(a, b), c)
            t = 6
            if a == b or b == c:
                t = 3
            if a == b == c:
                t = 1
            debug(g, t, a, b, c)
            ans += g * t
print(ans)

Submission status: Accepted

Solution code:
import math
from functools import reduce

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

k = int(input())
a = 0

for s in range(1,k+1):
    for t in range(1,k+1):
        for u in range(1,k+1):
            
            a += gcd(s,t,u)

print(a)

Submission status: Accepted

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

if __name__ == '__main__':
    main()