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 itertools
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())

# 同じものが出てくるので、それを削減させる
# N^3の計算数が必要　1<=K<=200

# 1 + 3 + 3 + 1 = 8
permutaions = list(itertools.combinations_with_replacement(
    list(range(1, K + 1)), 3))
count = 0
for permutaion in permutaions:
    # print(permutaion, gcd(permutaion[0], permutaion[1], permutaion[2]))
    if permutaion[0] == permutaion[1] and permutaion[1] == permutaion[2]:
        count += gcd(permutaion[0], permutaion[1], permutaion[2])
    elif permutaion[0] != permutaion[1] and permutaion[1] != permutaion[2] and permutaion[0] != permutaion[2]:
        count += (6 * gcd(permutaion[0], permutaion[1], permutaion[2]))
    else:
        count += (3 * gcd(permutaion[0], permutaion[1], permutaion[2]))
print(count)

Submission status: Accepted

Solution code:
# 2020/04/12
# AtCoder Beginner Contest 162 - C

# 最大公約数 fractions.gcdバージョン メモ化
# Greatest Common Divisor(GCD)  
import fractions
dp = [[0] * 201 for i in range(201)]
def gcd_fgf(a, b):
    if dp[a][b] == 0:
        if dp[b][a] == 0:
            dp[a][b] = fractions.gcd(a, b)
            return dp[a][b]
        else:
            return dp[b][a]
    else:
        return dp[a][b]

# Input
n = int(input())

# Calc
ans = 0
for a in range(1, n+1):
    for b in range(1, n+1):
        for c in range(1, n+1):
            wkgcd = gcd_fgf(a, b)
            ans = ans + gcd_fgf(wkgcd, c)

# Output
print(ans)

Submission status: Accepted

Solution code:
import math

a=input()
a=int(a)
sum=0

def gcda(x,y,z):
    temp=math.gcd(x,y)
    return math.gcd(temp,z)

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

print(sum)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def gcd(a,b):
  a,b=max(a,b),min(a,b)
  while b!=0:
    a,b=b,a%b
  return a
ct=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):
      ct+=gcd(gcd(i,j),k)
print(ct)

Submission status: Accepted

Solution code:
import math

k = int(input());

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

print(ans);

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
K = int(input())

# lcm & gcd not math library
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

from functools import reduce
def gcd_multi(num_list):
    return reduce(gcd, num_list)

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:
                dup_num = 1
            elif i == j or j == k:
                dup_num = 3
            else:
                dup_num = 6
            ans += gcd_multi([i, j, k]) * dup_num

print(ans)

Submission status: Accepted

Solution code:
import math

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

Submission status: Accepted

Solution code:
def main():
    import math

    K = int(input())

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

    print(total_ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

K = int(input())

S=0

for a in range(1,K+1):
    p=a
    for b in range(p+1,K+1):
        q=b
        for c in range(q+1,K+1):
            g=math.gcd(a,b)
            g=math.gcd(g,c)
            S=S+6*g
for a in range(1,K+1):
    p=a
    for b in range(p+1,K+1):
        g=math.gcd(a,b)
        S=S+6*g
for a in range(1,K+1):
    S=S+a
print(S)

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

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, Counter, deque
from itertools import accumulate, permutations, combinations
from operator import itemgetter
from bisect import bisect_left, bisect_right, bisect
from heapq import heappop, heappush
from fractions import gcd
from math import ceil, floor, sqrt, cos, sin, pi
from copy import deepcopy

# If you use recursive call, uncomment this code
#sys.setrecursionlimit(10**6)

def main():
    K = int(input())
    ans = 0
    # a,a,a
    ans += sum(range(1,K+1))

    # a,b,b
    tmp = 0
    memo = defaultdict(int)
    for a in range(1,K+1):
        for b in range(a+1,K+1):
            memo[(a,b)] = memo[(b,a)] = gcd(a,b)
            tmp += memo[(a,b)]
    ans += tmp * 6

    # a,b,c
    tmp = 0
    for a in range(1,K+1):
        for b in range(a+1,K+1):
            for c in range(b+1,K+1):
                ab = memo[(a,b)] if memo[(a,b)] else gcd(a,b)
                memo[(a,b)] = memo[(b,a)] = ab
                abc = memo[(ab,c)] if memo[(ab,c)] else gcd(ab,c)
                memo[(ab,c)] = memo[(c,ab)] = abc
                tmp += abc
    ans += tmp * 6

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
from functools import reduce
from math import gcd

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

K = int(input())
ans = 0

for _ in range(1, K + 1):
    for b in range(1, K + 1):
        for c in range(1, K + 1):
            ans += gcd3(_, b, c)
print(ans)

Submission status: Accepted

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

###
# main
if(__name__ == '__main__'):
    # input
    k = int(input())

    sum = 0
    for a in range(1,k+1):
        cand_list = []
        for cand in range(int(math.sqrt(a)),0,-1):
            if a % cand == 0:
                cand_list.append(cand)
                cand_list.append(a//cand)
        cand_list.sort()

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

                gcd = 0
                for tgt in cand_list[::-1]:
                    if b % tgt == 0 and c % tgt == 0:
                        gcd = tgt
                        break

                if a != b:
                    if b != c:
                        gcd *= 6
                    else:
                        gcd *= 3
                elif b != c:
                    gcd *= 3

                sum += gcd

    print(sum)

# else:
    # do nothing

Submission status: Accepted

Solution code:
from math import gcd as g
r=range(1,int(input())+1)
s=0
for i in r:
    for j in r:
        for k in r:
            s+=g(g(i,j),k)
print(s)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

memo = [[[0]*201 for _ in range(201)] for _ in range(201)]
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)

def t_gcd(a,b,c):
    d = gcd(a,b)
    e = gcd(c,d)
    res = gcd(d,e)
    memo[a][b][c] = res
    memo[a][c][b] = res
    memo[b][a][c] = res
    memo[b][c][a] = res
    memo[c][b][a] = res
    memo[c][a][b] = res
    return res
ans = 0
K = int(input())
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            if memo[a][b][c] == 0:
                ans += t_gcd(a,b,c)
            else:
                ans += memo[a][b][c]
print(ans)

Submission status: Accepted

Solution code:
import math
N = int(input())
n = 0
for i in range(1, N+1):
    for j in range(1, N+1):
        a = i
        b = j
        c = math.gcd(a,b)
        for k in range(1, N+1):
            d = k
            e = math.gcd(c,d)
            n += e
print(n)

Submission status: Accepted

Solution code:
from math import gcd

K=int(input())
sum=0

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

Submission status: Accepted

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

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

print(a)

Submission status: Accepted

Solution code:
import math

def main():
  K = int(input())
  gcd = math.gcd

  total = 0

  ab = {i: {j: gcd(i, j) for j in range(1,K+1)} for i in range(1,K+1)}

  #print(ab)

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

  print(total)

main()

Submission status: Accepted

Solution code:
from math import gcd
from functools import reduce


k = int(input())


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

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


sum = 0
for i in range(1, k+1):
    for j in range(1, k+1):
        for l in range(1, k+1):
             sum += f_gcd(i,j,l)

print(sum)

Submission status: Accepted

Solution code:
import math
def g(a,b,c):
    ans=math.gcd(a,b)
    p=math.gcd(ans,c)
    return p
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=sum+g(i,j,k)
print(sum)

Submission status: Accepted

Solution code:
import sys
import time
input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
# import math
from math import gcd
import heapq
import bisect
from collections import defaultdict, Counter, deque
MOD = 10**9 + 7
INF = 10**21


def dijkstra(graph, start, n):
    h = []
    heapq.heappush(h, (0, start))
    costs = [INF for _ in range(n)]
    while h:
        cost, cur = heapq.heappop(h)
        if costs[cur] != INF:
            continue
        costs[cur] = cost
        for edge in graph[cur]:
            ecost, tgt = edge
            if costs[tgt] == INF:
                heapq.heappush(h, (cost + ecost, tgt))

    return costs


def dist(x1, y1, x2, y2):
    return math.sqrt(abs(x1 - x2) ** 2 + abs(y1 - y2) ** 2)


def main():
    K = getN()
    ans = 0
    for i in range(1, K+1):
        for j in range(1, K+1):
            for k in range(1, K+1):
                tmp = gcd(i, j)
                ans += gcd(tmp, k)
                # print(i,j,k,ans)

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

gl = [[0]*K for _ in range(K)]
for i in range(K):
    for j in range(K):
        gl[i][j] = math.gcd(i+1, j+1)

res = 0
for i in range(K):
    for j in range(K):
        for k in range(K):
            tmp = gl[i][j]
            res += gl[tmp-1][k]

print(res)

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


ans = ans * 3

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

six = 0
for i in range(1, K - 1):
    for j in range(i + 1, K):
        for k in range(j + 1, K + 1):
            tmp = math.gcd(i, j)
            six += math.gcd(tmp, k)
            
ans = ans + six * 6
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# C - Sum of gcd of Tuples (Easy)

k = int(input())

def gcd(x, y):
    if x==0:
        return y
    else:
        return gcd(y%x, x)

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

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())
print(ans[k-1])

Submission status: Accepted

Solution code:
k=int(input())
import math
d=0
for a in range(1,k+1):
    for b in range (1,k+1):
        f=math.gcd(a,b)
        for c in range (1,k+1):
            g=math.gcd(f,c)
            d+=g
print(d)

Submission status: Accepted

Solution code:
from sys import stdin
# import sys

# A, B, C = [int(x) for x in stdin.readline().rstrip().split()]
# A,B = [int(x) for x in stdin.readline().rstrip().split()]
# U = input().split()
# A, B = [str(x) for x in stdin.readline().rstrip().split()]

import math

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
#sys.setrecursionlimit(150000)
from math import gcd

mm=[[[0]*200 for i in range(200)] for j in range(200)]

def d(a,b,c):
    return gcd(gcd(a+1,b+1),c+1)

def solve(K: int):
    ans=0
    a=[0,0,0]
    for i in range(K):
        for j in range(K):
            for k in range(K):
                ans+=d(i,j,k)
                continue
    print(ans)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
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:
def euclid(a, b):
    if a == b:
        return a
    elif b > a:
        return euclid(b, a)
    else:
        while b > 0:
            temp = a % b
            a = b
            b = temp
        return a


d = {}
def euclid_memo(a, b):
    if a > b:
        c = b
        b = a
        a = c
    if a in d:
        if not b in d[a]:
            d[a][b] = euclid(a, b)
    else:
        d[a] = {}
        d[a][b] = euclid(a, b)
    return d[a][b]

def calc(K):
    x = 0
    for i in range(1, K + 1):
        for j in range(1, K + 1):
            for k in range(1, K + 1):
                d = euclid_memo(i, j)
                e = euclid_memo(d, k)
                x += e
    return x


K = int(input())
print(calc(K))

Submission status: Accepted

Solution code:
import math

k = int(input())

s = sum([math.gcd(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)])
print(s)

Submission status: Accepted

Solution code:
import math

k = int(input())
mp = [[-1] * k for _ in range(k)]

def gcd(a, b):
    if b == 0:
        return a
    if mp[a - 1][b - 1] == -1:
        mp[a - 1][b - 1] = gcd(b, a % b)
        return mp[a - 1][b - 1]
    return mp[a - 1][b - 1]


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(k, gcd(j, i))

print(ans)

Submission status: Accepted

Solution code:
import math
import itertools

n = int(input())
l = [i for i in range(1,n+1)]
l = itertools.product(l,l)


ans = 0
for x,y in l:
    g = math.gcd(x,y)
    for j in range(1,n+1):
        ans += math.gcd(j,g)
    
print(ans)

Submission status: Accepted

Solution code:
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)
a=int(input())
sum=0
for i in range(a):
    for j in range(a):
        for c in range(a):
            sum+=gcd(i+1,j+1,c+1)
print(sum)

Submission status: Accepted

Solution code:
import math

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

Submission status: Accepted

Solution code:
k = int(input())
gcd = [[0]*k for _ in range(k)]
def f(a,b):
    if a == b:
        return a
    else:
        if a > b:
            return f(a-b,b)
        else:
            return f(b-a,a)
for a in range(k):
    for b in range(k):
        gcd[a][b]=f(a+1,b+1)

ans = 0
for a in range(k):
    for b in range(k):
        for c in range(k):
            ans += gcd[gcd[a][b]-1][c]
        
print(ans)

Submission status: Accepted

Solution code:
def main():
    import math
    import sys

    input = sys.stdin.readline

    n = int(input())
    c_1 = 0
    c_2 = 0
    c_3 = 0

    for i in range(n):
        for j in range(i,n):
            gc = math.gcd(i+1,j+1)
            for k in range(j,n):
                if i == j and j == k:
                    c_1  += i+1
                elif i != j and j != k and k != i:
                    c_2 += math.gcd(gc,k+1)
                else:
                    c_3 += math.gcd(i+1,k+1)

    print(c_1 + c_2 * 6 + c_3 * 3)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
K = int(input())
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 and b != c and c != a:
        ans += math.gcd(math.gcd(a,b),c) * 6
      elif a == b and b == c:
        ans += math.gcd(math.gcd(a,b),c)
      else:
        ans += math.gcd(math.gcd(a,b),c) * 3
print(ans)

Submission status: Accepted

Solution code:
import math
from functools import reduce

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

K =int(input())
sum = 0

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

Submission status: Accepted

Solution code:
from math import gcd
def main():
    k = int(input())
    r = 0
    for ia in range(1, k + 1):
        for ib in range(1, k + 1):
            for ic in range(1, k + 1):
                t1 = gcd(ib, ic)
                r += gcd(t1,ia)
    print(r)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


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


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


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

    res = 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) & (j == k):
                    same = 1
                elif (i == j) | (j == k) | (k == i):
                    same = 3
                else:
                    same = 6
                res += trigcd(i,j,k) * same

    print(res)



main()

Submission status: Accepted

Solution code:
from math import gcd
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,gcd(b,c))
      
print(ans)

Submission status: Accepted

Solution code:
import math
n=int(input())
count=0
for a in range(n):
    for b in range(n):
        for c in range(n):
            gcd_f=math.gcd(a+1,b+1)
            gcd_s=math.gcd(gcd_f,c+1)
            count+=gcd_s
print(count)

Submission status: Accepted

Solution code:
def gcd_trio(a, b, c):
  return gcd(gcd(a, b), c)

def gcd(a, b):
  if a < b:
    a, b = b, a
  if b == 0:
    memo[a][b] = a
    return memo[a][b]

  if memo[a][b] != 0:
    return memo[a][b]
  else:
    memo[a][b] = gcd(b, a%b)
    return memo[a][b]

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

total_gcd = 0
for i in range(1, K + 1):
  for j in range(1, K + 1):
    for k in range(1, K + 1):
      total_gcd += gcd_trio(i, j, k)

print(total_gcd)

Submission status: Accepted

Solution code:
from sys import setrecursionlimit, exit
setrecursionlimit(1000000000)


def main():
    K = int(input()) + 1
    ans = 0
    for i in range(1, K):
        ans += i
        for j in range(i + 1, K):
            def GCD(x, y):
                return GCD(y, x%y) if y else x
            ans += GCD(i, j) * 6
            for k in range(j + 1, K):
                gcd = 1
                mx = min(i, j, k)
                for l in range(2, K):
                    if i % l == 0 and j % l == 0 and k % l == 0:
                        gcd = l
                    if l == mx:
                        break
                ans += gcd * 6
    print(ans)

main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
k=int(input())

def gcd(x,y):
    if y==0:
        return x
    else:
        return gcd(y,x%y)

ans=0
import itertools
for x in itertools.product(range(1,k+1),repeat=3):
    a,b,c=x
    ans+=gcd(gcd(a,b),c)
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from functools import reduce

input = sys.stdin.readline

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

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

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

    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import math
MOD = 10**9
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

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 i==k: g = i
            elif (i==j and i!=k):
                g = math.gcd(i,math.gcd(j,k))*3
            elif (i==k and i!=j):
                g = math.gcd(i,math.gcd(j,k))*3
            elif (j==k and i!=j):
                g = math.gcd(i,math.gcd(j,k))*3
            else : g = math.gcd(i,math.gcd(j,k))*6
            ans += g
print(ans)

Submission status: Accepted

Solution code:
k = int(input())
s = 0
import math
from functools import reduce
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):
      s += math.gcd(g,c)
print(s)

Submission status: Accepted

Solution code:
import math

K = int(input())
con = 0
con2 = 0
con3 = 0

for i in range(K):
    for k in range(i, K):
        tmp = math.gcd(i+1, k+1)
        for l in range(k, K):
            pre = math.gcd(tmp, l+1)
            con += pre
            if i == k == l:
                con3 += pre
                continue
            elif i == k or k == l or l == i:
                con2 += pre
                continue
            

print(con*6 - con2*3 - con3*5)

Submission status: Accepted

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())
from math import gcd

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

    cache = {}
    def gcd3(a, b, c):
        ab = gcd(a, b)
        if ab == 1:
            return 1


    ans = K * K + K * (K-1) + (K-1)**2
    ans += (K-1) * (2+K) // 2
    K += 1

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

    for i in range(2, K):
        for j in range(2, K):
            if i == j:
                continue
            ans += 3 * gcd(i, j)
    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import math
import itertools

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

n=int(input())
ans=0
lis = [i for i in range(1,n+1)]
for v in itertools.combinations_with_replacement(lis, 3):
    a=math.gcd(v[0],v[1])
    ans+=math.gcd(a,v[2])*permutations_count(3, len(set(v))-1)
print(ans)

Submission status: Accepted

Solution code:
import itertools
import math

N = int(input())
n_s = list(range(1, N + 1))
ans = 0
for l in itertools.product(n_s, n_s, n_s):
    a, b, c = sorted(l)
    ans += math.gcd(c, math.gcd(b, a))

print(ans)

Submission status: Accepted

Solution code:
import math
k=int(input())
ans=0
for i in range(1,k+1):
  for j in range(1,k+1):
    b=math.gcd(i,j)
    for l in range(1,k+1):
      a=math.gcd(b,l)
      ans+=a
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):
        g = gcd(a,b)
        if g == 1:
            ans += K
        else:
            for c in range(1,K+1):
                ans += gcd(g,c)

print(ans)

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    from math import gcd
    input = sys.stdin.readline

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


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:
import math
import copy
import sys
import fractions
# import numpy as np
# import statistics
import decimal
import heapq
import collections
import itertools
import bisect

# from operator import mul

sys.setrecursionlimit(100001)


# input = sys.stdin.readline
# sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputIntList():
    outputDataList = []
    inputData = input().split()
    outputDataList = [int(n) for n in inputData]

    return outputDataList


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===


n = int(input())


ans = 0
dic = {}

for i in range(1, n+1):
    for j in range(1, n+1):
        tmp = math.gcd(i,j)
        if tmp in dic:
            dic[tmp] += 1
        else:
            dic[tmp] = 1

for key in dic:
    for i in range(1, n+1):
        ans += math.gcd(key, i) * dic[key]

print(ans)

Submission status: Accepted

Solution code:
K = int(input())

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

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

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(gcdtable[i][j],k)


print(ans)

Submission status: Accepted

Solution code:
import math
from functools import reduce
from itertools import combinations_with_replacement
k = int(input())
def gcd(*numbers):
    return reduce(math.gcd, numbers)

ls = [i for i in range(1,k+1)]
h = combinations_with_replacement(ls, 3)
ans = 0
for v in h:
    a,b,c = v
    if len(set(v)) ==1:
        ans += math.gcd(math.gcd(a,b),c)
    elif len(set(v)) == 2:
        ans += 3 * math.gcd(math.gcd(a,b),c)
    else:
        ans += 6 * math.gcd(math.gcd(a,b),c)
print(ans)

Submission status: Accepted

Solution code:
import math
N = int(input())
a = [[math.gcd(i, j) for j in range(1, N+1)] for i in range(1, N+1)]
s = [sum(a[i]) for i in range(N)]
ans = 0
for i in range(N):
  for j in range(N):
    ans = ans + s[a[i][j]-1]
print(ans)

Submission status: Accepted

Solution code:
k = int(input())
 
def gcd(a, b):
    while True:
        r = a % b
        a, b = b, r
        if b == 0:
            return a
    
def gcds(a, b, c):
    d = gcd(a, b)
    return gcd(c, d)
 
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 += gcds(i, j, l)
            elif (i != j) and(j != l) and (l != i):
                ans += 6*gcds(i, j, l)
            else:
                ans += 3*gcds(i, j, l)
print(ans)