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: Time Limit Exceeded

Solution code:
#
# Written by NoKnowledgeGG @YlePhan
# ('ω')
#
#import math
#mod = 10**9+7
#import itertools
#import fractions
#import numpy as np
#mod = 10**4 + 7
"""def kiri(n,m):
  r_ = n / m
  if (r_ - (n // m)) > 0:
    return (n//m) + 1
  else:
    return (n//m)"""

""" n! mod m 階乗
mod = 1e9 + 7
N = 10000000
fac = [0] * N
def ini():
  fac[0] = 1 % mod
  for i in range(1,N):
    fac[i] = fac[i-1] * i % mod"""

"""mod = 1e9+7
N = 10000000
pw = [0] * N
def ini(c):
  pw[0] = 1 % mod
  for i in range(1,N):
    pw[i] = pw[i-1] * c % mod"""

"""
def YEILD():
  yield 'one'
  yield 'two'
  yield 'three'
generator = YEILD()
print(next(generator))
print(next(generator))
print(next(generator))
"""
"""def gcd_(a,b):
  if b == 0:#結局はc,0の最大公約数はcなのに
    return a
  return gcd_(a,a % b) # a = p * b + q"""
"""def extgcd(a,b,x,y):
  d = a
  if b!=0:
    d = extgcd(b,a%b,y,x)
    y -= (a//b) * x
    print(x,y)
  else:
    x = 1
    y = 0
  return d"""

# 最大公約数 と 最小公倍数
"""def gcd(a,b):
  if b == 0:
    return a
  return gcd(b, a % b)
def lcm(a,b):
  g = gcd(a,b)
  return (a * b) // g"""

# 二分探索
"""import bisect # 二分探索
print(A,bisect.bisect_left(A,4))
print(C,n - bisect.bisect_right(C,4))
print(sum(bisect.bisect_left(A,b) * (n-bisect.bisect_right(C,b)) for b in B))"""

# 円周率 pi
"""import math
pi_ = math.pi"""

# エラトステネスの篩
"""def Erato(n):
    prime = []
    is_prime = [True] * (n+1)
    p = 0
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2,n+1):
      if is_prime[i] == True:
        prime.append(i)
        p += 1
        for j in range(2 * i,n+1,i):
          is_prime[j] = False
    return p"""

def readInts():
  return list(map(int,input().split()))
mod = 10**9 + 7
def main():
  from fractions import gcd
  from functools import reduce
  k = int(input())
  
  ans = 0
  for a in range(1,k+1):
    for b in range(1,k+1):
      for c in range(1,k+1):
        ans += reduce(gcd,(a,b,c))
  print(ans)
if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import fractions
x=0
K=int(input())
for i in range(1,K+1):
  for j in range(1,K+1):
    for h in range(1,K+1):
      if i==j and j==h:
        x=x+i
      elif i==j or j==h:
        x=x+fractions.gcd(i,h)
      else:
        x=x+fractions.gcd(i,fractions.gcd(j,h))
print(x)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools

if __name__ == "__main__":
    K = int(input())+1
    ret = 0
    for a, b, c in itertools.product(range(1,K), range(1,K), range(1,K)):
        ret += np.gcd.reduce([a,b,c])
    print(ret)

Submission status: Time Limit Exceeded

Solution code:
K = int(input())
ans = 0
for A in range(1, K+1):
  for B in range(1, K+1):
    a = A
    b = B
    gcd_AB = 0
    while gcd_AB == 0:
      if a > b:
        a = a + b
        b = a - b
        a = a - b # 必ず c <= d になる
      if b%a == 0:
        gcd_AB = a
      else:
        b = b%a
    for C in range(1, K+1):
      c = C
      gcd_ab = gcd_AB
      gcd_ABC = 0
      while gcd_ABC == 0:
        if gcd_ab > c:
          gcd_ab = gcd_ab + c
          c = gcd_ab - c
          gcd_ab = gcd_ab - c # 必ず c <= d になる
        if c%gcd_ab == 0:
          gcd_ABC = gcd_ab
        else:
          c = c%gcd_ab
      ans += gcd_ABC
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
# メモを残す
K = int(input()) + 1
dic = {}
ans = 0
for a in range(1,K):
    for b in range(1,K):
        for c in range(1,K):
            # 大きい順にソートする
            l = tuple(sorted([a,b,c]))
            if l in dic:
                ans += dic[l]
            else:
                # 最大公約数を求める
                tmp_l = tuple([l[0], l[1]])
                if tmp_l in l:
                    gcd_ab = l[tmp_l]
                else:
                    gcd_ab = math.gcd(l[0], l[1])
                    dic[tmp_l] = gcd_ab

                if gcd_ab < c:
                    tmp_l = tuple([gcd_ab, c])
                else:
                    tmp_l = tuple([c, gcd_ab])

                if tmp_l in l:
                    gcd = l[tmp_l]
                else:
                    gcd = math.gcd(gcd_ab, c)
                    dic[tmp_l] = gcd
                dic[l] = gcd
                ans+=gcd
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce

K = int(input())

def GCD(x):
    return reduce(math.gcd, x)

s = 0
for i in range(1, K + 1):
    for j in range(1, K + 1):
        for h in range(1,K + 1):
            s += GCD((i, j, h))

print(s)

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
    
k = int(input())
l1 = range(1, k+1)
s = 0

for a in l1:
    for b in l1:
        for c in l1:
            l2 = [a, b, c]
            g1 = gcd(a,b)
            g2 = gcd(g1, c)
            s += g2
print(s)

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
from functools import reduce

def func(a,b,c):
  if a == b and b == c:
    return a
  elif a == b and b !=c:
    return gcd(a,c)
  elif a != b and b ==c:
    return gcd(a,b)
  else:
    return reduce(gcd,(a,b,c))

k = int(input())
li = []
for a in range(1,k+1):
  for b in range(1,k+1):
    for c in range(1,k+1):
      li.append(func(a,b,c))

print(sum(li))

Submission status: Time Limit Exceeded

Solution code:
import itertools
import fractions

N = input()
N = int(N)

l = list(itertools.combinations_with_replacement(list(range(1,N+1)), 3))
s_all = 0
for nums in l:
    count = 0
    ans = nums[0]
    for i in range(1, 3):
        ans = fractions.gcd(ans, nums[i])
    a,b,c = nums[0], nums[1], nums[2]
    if a==b:
        count+=1
    if a==c:
        count+=1
    if b==c:
        count+=1

    if count==0:
        num = 6
    elif count==1:
        num=3
    elif count==3:
        num=1
    s_all += ans*num
print(s_all)

Submission status: Time Limit Exceeded

Solution code:
import math
import fractions

K = int(input())
sum = 0

def gcd(x,y,z):
    a = [x,y,z]
    ans = a[0]
    for i in range(1,len(a)):
        ans = math.gcd(ans,a[i])
    return ans

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


print(sum)


"""
import fractions
a = list(map(int, input().split()))
ans = a[0]
for i in range(1, N):
    ans = fractions.gcd(ans, a[i])
print(ans)
"""

Submission status: Time Limit Exceeded

Solution code:
def gcd1(a, b):
  c = 0
  if b > a:
    c = b
    b = a
    a = c
  if a % b == 0:
    return b
  else:
    return gcd1(b, a % b)

def gcd2(a, b, c):
  d = gcd1(a, b)
  if d > c:
    return gcd1(d, c)
  else:
    return gcd1(c, d)

k = int(input())

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

print(sum)

Submission status: Time Limit Exceeded

Solution code:
#C - Sum of gcd of Tuples (Easy)
K = int(input())
sum = 0

import fractions
def N_gcd(ans):
    ans2 = ans[0]
    for n in range(1, 3):
        ans2 = fractions.gcd(ans2, ans[n])
    return ans2

for i in range(1,K+1):
    for j in range(1,K+1):
            for k in range(1,K+1):
                a = [i,j,k]
                sum += N_gcd(a)


print(sum)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce
 
k = int(input())
 
def gcd(*numbers):
    return reduce(math.gcd, numbers)
 
lst = []
for i in range(k):
    a = i + 1
    for j in range(k):
        b = j + 1
        for l in range(k):
            c = l + 1
            koyakusu = gcd(a, b, c)
            lst.append(koyakusu)
kotae = sum(lst)
print(kotae)

Submission status: Time Limit Exceeded

Solution code:
memo = [
    [
        [ -1 ] * 201
    ] * 201
] * 201

def gcd(numbers):
    numbers.sort()
    a = numbers[1]
    b = numbers[0]
    ans = b
    while True:
        q, mod = divmod(a, b)
        if mod == 0:
            break
        a = b
        b = mod
        ans = mod
    return ans

K = int(input())
numbers = []
for i in range(K, 0, -1):
    for j in range(i, 0, -1):
        for k in range(j, 0, -1):
            numbers.append([i, j, k])

sum = 0
for number in numbers:
    dup = len(set(number))
    if dup == 1:
        sum += gcd([gcd([number[0], number[1]]), number[2]])
    elif dup == 2:
        sum += gcd([gcd([number[0], number[1]]), number[2]]) * 3
    else:
        sum += gcd([gcd([number[0], number[1]]), number[2]]) * 6

print(sum)

Submission status: Time Limit Exceeded

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

result = 0

# 3つとも等しい数字
for i in range(1, k+1):
    result += i

# 2つが等しくて、1つが異なる数字
for set in list(itertools.combinations(range(1, k+1), 2)):
    result += (gcd(set[0], set[1]))*6

# 3つとも異なる
for set in list(itertools.combinations(range(1, k+1), 3)):
    result += (gcd(gcd(set[0], set[1]), set[2]))*6

print(result)

Submission status: Time Limit Exceeded

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

k = int(input())

ans_list = []

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)
            ans_list.append(ans)
print(sum(ans_list))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import fractions
import sys
readline = sys.stdin.buffer.readline
s =int(readline().rstrip().decode())
def gcdsp(x,y,z):
    t =fractions.gcd(x,y)
    return fractions.gcd(t,z)
res = 0
for i in range(s):
    for j  in range(s):
        for k  in range(s):
            if i < j and j <= k:
                res += gcdsp(i+1, j+1, k+1)
res1 = int((s + 1)*s/2)
print(6*res+res1)

Submission status: Time Limit Exceeded

Solution code:
def gcd(m,n,o):
    x = int(max(int(m), int(n)))
    y = int(min(m, n))
    if x % y == 0:
        a = int(max(int(y), int(o)))
        b = int(min(int(y), int(o)))
        if a % b == 0:
            return b
        else:
            while a % b != 0:
                c =a % b
                a = b
                b = c
            else:
                return c
    else:
        while x % y != 0:
            z = x % y
            x = y
            y = z
        else:
            d = int(max(int(z), int(o)))
            e = int(min(int(z), int(o)))
        if d % e == 0:
            return e
        else:
            while d % e != 0:
                f = d % e
                d = e
                e = f
            else:
                return f

input_k = int(input())
output = 0

for i in range(1, input_k + 1):
    for j in range(1, input_k + 1):
        for k in range(1, input_k + 1):
            output += gcd(i, j, k)

print(output)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
k = int(input())

def f_gcd(x,y):#x>y
    ans = y
    while x%y != 0:
        y = x%ans
        x = ans
        ans = y
    return ans

s = 0
for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            gcd_ab = 0
            gcd = 0
            if a >= b:
                gcd_ab = f_gcd(a,b)
            else:
                gcd_ab = f_gcd(b,a)
            
            if gcd_ab >= c:
                gcd = f_gcd(gcd_ab,c)
            else:
                gcd = f_gcd(c,gcd_ab)
            s = s+gcd
print(s)

Submission status: Time Limit Exceeded

Solution code:
y=int(input())
b=[[i,j,k]  for i in range(1,y+1) for j in range(1,y+1) for k in range(1,y+1) ]
c=[]
for l in range(y**3):
    import math
    a = b[l]
    if a[0]==1 or a[1]==1 or a[2]==1:
        c.append(1)
    elif a[0]==a[1]==a[2]:
        c.append(a[0])    
    else:    
        ans1 = math.gcd(a[0], a[1])
        ans2 =math.gcd(ans1,a[2])
        c.append(ans2)
print(sum(c))

Submission status: Time Limit Exceeded

Solution code:
import math

X = int(input())
sum = 0


for i in range(1,X+1):
    for j in range(1, X+1):
        for k in range(1, X+1):
                a = math.gcd(math.gcd(i,j),k)
                sum = sum + a
print(sum)

Submission status: Time Limit Exceeded

Solution code:
#
# Written by NoKnowledgeGG @YlePhan
# ('ω')
#
#import math
#mod = 10**9+7
#import itertools
#import fractions
#import numpy as np
#mod = 10**4 + 7
"""def kiri(n,m):
  r_ = n / m
  if (r_ - (n // m)) > 0:
    return (n//m) + 1
  else:
    return (n//m)"""

""" n! mod m 階乗
mod = 1e9 + 7
N = 10000000
fac = [0] * N
def ini():
  fac[0] = 1 % mod
  for i in range(1,N):
    fac[i] = fac[i-1] * i % mod"""

"""mod = 1e9+7
N = 10000000
pw = [0] * N
def ini(c):
  pw[0] = 1 % mod
  for i in range(1,N):
    pw[i] = pw[i-1] * c % mod"""

"""
def YEILD():
  yield 'one'
  yield 'two'
  yield 'three'
generator = YEILD()
print(next(generator))
print(next(generator))
print(next(generator))
"""
"""def gcd_(a,b):
  if b == 0:#結局はc,0の最大公約数はcなのに
    return a
  return gcd_(a,a % b) # a = p * b + q"""
"""def extgcd(a,b,x,y):
  d = a
  if b!=0:
    d = extgcd(b,a%b,y,x)
    y -= (a//b) * x
    print(x,y)
  else:
    x = 1
    y = 0
  return d"""

# 最大公約数 と 最小公倍数
"""def gcd(a,b):
  if b == 0:
    return a
  return gcd(b, a % b)
def lcm(a,b):
  g = gcd(a,b)
  return (a * b) // g"""

# 二分探索
"""import bisect # 二分探索
print(A,bisect.bisect_left(A,4))
print(C,n - bisect.bisect_right(C,4))
print(sum(bisect.bisect_left(A,b) * (n-bisect.bisect_right(C,b)) for b in B))"""

# 円周率 pi
"""import math
pi_ = math.pi"""

# エラトステネスの篩
"""def Erato(n):
    prime = []
    is_prime = [True] * (n+1)
    p = 0
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2,n+1):
      if is_prime[i] == True:
        prime.append(i)
        p += 1
        for j in range(2 * i,n+1,i):
          is_prime[j] = False
    return p"""

def readInts():
  return list(map(int,input().split()))
mod = 10**9 + 7
def main():
  import fractions
  k = int(input())
  L = []
  ans = 0
  for a in range(1,k+1):
    for b in range(1,k+1):
      L.append(fractions.gcd(a,b))
  Llen = len(L)
  for c in range(1,k+1):
    for i in range(0,Llen):
      ans += fractions.gcd(c,L[i])
  print(ans)
if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np


def sum_gcd(k: int) -> int:
    cache = np.zeros((k + 1, k + 1, k + 1), dtype=int)

    def cached_gcd(a: int, b: int, c: int) -> int:
        k0, k1, k2 = sorted([a, b, c])

        result = cache[k0][k1][k2]
        if result > 0:
            return result
        else:
            result = math.gcd(math.gcd(k0, k1), k2)
            cache[k0][k1][k2] = result
            return result

    answer = 0
    for h in range(1, k + 1):
        for i in range(1, k + 1):
            for j in range(1, k + 1):
                answer += cached_gcd(h, i, j)

    return answer


def main():
    k = int(input().rstrip())
    print(sum_gcd(k))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import fractions
import itertools

k = int(input())

gcd_map = [[-1 for i in range(1,k+1)]for j in range(1,k+1)]

ans = 0
for a in range(1,k+1):
    for b in range(1,k+1):
        for c in range(1,k+1):
            if gcd_map[a-1][b-1]==-1:
                gab = fractions.gcd(a,b)
                gcd_map[a-1][b-1] = gab
                gcd_map[b-1][a-1] = gab
            
            else:
                gab = gcd_map[a-1][b-1]
            
            if gcd_map[gab-1][c-1]==-1:
                gbc = fractions.gcd(gab,c)
                gcd_map[gab-1][c-1] = gbc
                gcd_map[c-1][gab-1] = gbc

            else:
                gbc = gcd_map[gab-1][c-1]

            ans+=gbc
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce

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

K=int(input())

i=1
j=1
k=1
r=0
list=[2,3,5,7,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199]

while(i<K+1):
  j=1
  f=0
  if(f in list == True):
    f=1
  while(j<K+1):
    k=1
    g=0
    if(g in list == True):
      g=1
    while(k<K+1):
      h=0
      if(h in list == True):
        h=1
      if(i==1 or j==1 or k==1):
        r+=1
      elif(f==1 and g==1 and h==1):
        if(i==j and j==k):
          r+=i
        else:
          r+=1
      else:
        r+=gcd(i, j, k)
      k+=1
    j+=1
  i+=1

print(r)

Submission status: Time Limit Exceeded

Solution code:
import math

k = int(input())

sum = 0
i, j = 0, 0
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            i = math.gcd(a, b)
            j = math.gcd(i, c)
            sum += j

print(sum)

Submission status: Time Limit Exceeded

Solution code:
import math
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=sum+math.gcd(math.gcd(a,b),c)
print(sum)

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce

K = int(input())

# K = 2


def gcd(*numbers):
    return reduce(math.gcd, 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(a, b, c)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
from fractions import gcd
from copy import deepcopy
import math
import queue
#import sympy as syp(素因数分解とか)
Mod = 1000000007
import sys
sys.setrecursionlimit(100000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

def main(): #startline-------------------------------------------
    k = int(input())
    ans = 0
    for i in range(1,k+1):
        for j in range(i,k+1):
            for l in range(j,k+1):
                ans += gcd(gcd(i,j),l)*6//math.factorial(4-len(set([i,j,l])))
    print(ans)
if __name__ == "__main__":
    main() #endline===============================================

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

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

def gcd(x, y, z):
    return gcd2(gcd2(x, y), z)


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

Submission status: Time Limit Exceeded

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

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

def main():
    N = list(map(int, open(0).read().split()))
    N = N[0]
    L = 0

    for a in range(1, N+1):
        for b in range(1, N+1):
            for c in range(1, N+1):
                L += gcd(a,b,c)
    print(L)
main()

Submission status: Time Limit Exceeded

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from itertools import combinations_with_replacement

def gcd_memo(memo, a, b):
    if memo[a][b] > 0:
        return memo[a][b]
    res = np.gcd(a, b)
    memo[a][b] = res
    memo[b][a] = res
    return res

def main():
    k = int(input())
    res = 0
    memo = np.zeros((k+1, k+1), int)
    for c in combinations_with_replacement(range(1,k+1), 3):
        ab = gcd_memo(memo, c[0], c[1])
        abc = gcd_memo(memo, ab, c[2])
        l = len(set(c))
        mul = 1
        if l == 2:
            mul = 3
        elif l == 3:
            mul = 6
        res += abc * mul
    print(res)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
import itertools
from functools import reduce

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

k = int(input())

ans = 0 
comb_list  = itertools.product(range(1,k + 1), repeat=3)

for a,b,c in comb_list:
    s = gcd(a,b,c)
    ans += s
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 初期入力
K =int(input())

# 最小約数(mathは3.5以降) 
from functools import reduce
import math #(2020-0405  fractions→math)
def lcm_base(x, y):
    return  math.gcd(x, y) # 「//」はフロートにせずにintにする
def lcm_list(numbers):
    return reduce(lcm_base, numbers)

#

saisyou_koyakusu =[]
"""
for i in range(1,K+1):
    for j in range(1,K+1):
        for l in range(1,K+1):
            saisyou_koyakusu.append(lcm(i,j,l))

"""            #print(i,j,l)

from itertools import product
# ["a", "b", "c"] の並べ替えをすべて列挙する
a= [i for i in range(1,K+1)]
for t in product(a,repeat=3):
    #print(t)
    saisyou_koyakusu.append(lcm_list(list(t)))
    
print(sum(saisyou_koyakusu))

Submission status: Time Limit Exceeded

Solution code:
import math
n=int(input())
g=0
for i in range(1,n+1):
    for j in range(1,n+1):
        for h in range(1,n+1):
            d=math.gcd(i,j)
            f=math.gcd(h,d)
            g=g+f
print(g)

Submission status: Time Limit Exceeded

Solution code:
import math
import itertools

from functools import reduce

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

#def gcd_list(numbers):
#    return reduce(math.gcd, numbers)
    
N=int(input())
GCD=[]
GCD1=[]
for i in range (1,N+1):
    GCD.append(i)
#print(GCD)
for i in itertools.product(GCD,repeat=3):
    
#for i in itertools.combinations_with_replacement(GCD,3):
    GCD1.append(gcd(i[0],i[1],i[2]))
    #print(gcd(i[0],i[1],i[2]))
    #print(i)
   # print(GCD)
#print(GCD)
print(sum(GCD1))

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

k = int(input())
ans = 0
g = []

for a in range(1,k+1):
  g.append(a)

o = []
for b in range(1,k+1):
    for i in g:
      o.append(gcd(b,i))


for c in range(1, k+1):
  for i in o:
    ans += gcd(c,i)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())

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

def gcdlist(l):
    a = l[0]
    for i in range(len(l)):
        a = gcd(a,l[i])
    return a

num = 0
for i in range(1, n+1):
    for j in range(1, n+1):
        for k in range(1, n+1):
            num += int(gcdlist([i, j, k]))

print(num)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import math
from functools import reduce
import collections
def gcd_list(numbers):
    return reduce(math.gcd,numbers)
K=int(input())
ans=0
x=list(itertools.combinations_with_replacement(range(1,K+1),3))
for i in x:
  c=collections.Counter(i)
  if max(c.values())==1:
    ans+=6*gcd_list(i)
  elif max(c.values())==2:
    ans+=3*gcd_list(i)
  else:
    ans+=gcd_list(i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def gcd(m,n):
  x = max(m,n)
  y = min(m,n)
  if x % y == 0:
    return y
  else:
    while x % y != 0:
      z = x % y
      x = y
      y = z
    else:
      return z
K = int(input())
x = 0
y = 0
z = 0
 
for i in range(1, K+1):
  for k in range(1, K+1):
    x = gcd(i,k)
    for j in range(1, K+1):
      y = gcd(x, j)
      z += y
print(z)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
output_list = []

def gcd(a, b, c):
  ret_gcd = 0
  mini = min([a,b,c])
  for i in range(mini, 0, -1):
    if a % i == 0 and b % i == 0 and c % i == 0:
      ret_gcd = i
      break
  return ret_gcd

for a in range(1, N+1):
  for b in range(1, N+1):
    for c in range(1, N+1):
      output_list.append(gcd(a, b, c))

print(sum(output_list))

Submission status: Time Limit Exceeded

Solution code:
import math

k = int(input())

g =[math.gcd(math.gcd(i+1, j+1), l+1) for i in range(k) for j in range(k) for l in range(k)]
print(sum(g))

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce

s = 0
k = int(input())

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):
            s += gcd(a,b,c)
            
print(s)

Submission status: Time Limit Exceeded

Solution code:
import itertools

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
  
K = int(input())
cnt = sum([gcd(gcd(a,b),c) for a,b,c 
           in itertools.product(range(1,K+1), range(1,K+1), range(1,K+1))])   
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import math
# from itertools import product
from functools import reduce

def main():
    def gcd(*numbers): return reduce(math.gcd, numbers)
    K = int(input())
    ans = 0
#     valiation = list(itertools.product(range(1, K+1), repeat=3))
#     for v in valiation:
#         ans += gcd(v)
    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)
        
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import functools

K = int(input())

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

def gcd3(nums):
    return functools.reduce(euclid, nums)

nums = []
gcds = []
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            nums.append(a)
            nums.append(b)
            nums.append(c)
            gcds.append(gcd3(nums))
            nums.clear()

print(sum(gcds))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)
ans = 0
N = int(input())
L = []
for x in range(1,N+1):
    for y in range(1,N+1):
       if(x == y):
           L.append(x)
       elif(x % y == 0):
           L.append(y)
       elif(y % x == 0):
           L.append(x)
       else:
           L.append(gcd(x,y))
for x in L:
    for z in range(1,N+1):
       if(x == z):
           ans += x 
       elif(x % z == 0):
           ans += z
       elif(z % x == 0):
           ans += x
       else:
           ans += gcd(x,z)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
K = int(input())

import fractions

res = 0


for i in range(1, K+1):
    for j in range(1, K+1):
        for l in range(1, K+1):
            a = list([i, j, l])
            ans = a[0]
            for n in range(1, 3):
                ans = fractions.gcd(ans, a[n])
            res += ans

print(res)

Submission status: Time Limit Exceeded

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())
A =[]


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


ans = 0
for i in range(len(A)):
    ans += gcd_list(A[i])
            
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
cnt=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):
            cnt+=math.gcd(math.gcd(i,j),l)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
K = int(input())
K_list = []
for i in range(1, K+1):
    K_list = [i] + K_list

ans = 0

def gcd(a, b, c):
    for i in K_list:
        if a % i == b % i == c % i == 0:
            return i


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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

def gcd_3(a,b,c):
    p = gcd(a,b)
    q = gcd(p,c)
    return q

k = int(input())
ans = 0

num = list(itertools.product(range(1,k+1),range(1,k+1),range(1,k+1)))

for l in num:
    a,b,c = l
    ans += gcd_3(a,b,c)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
import itertools, math
# print("Start")
# N = list(map(str, input().split()))
N = int(input())

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

out = []
for i in range(1, N+1):
    for j in range(1, N+1):
        for k in range(1, N+1):
            X = gcd_list([i,j,k])
            out.append(X)
            # print(out)

print(sum(out))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
import math
a=[0]*3
sum=0
for i in range(n):
  for j in range(n):
    for k in range(n):
      a[0]=i+1
      a[1]=j+1
      a[2]=k+1
      ans=a[2]
      for l in range(2):
        ans = math.gcd(ans, a[l])
      sum+=ans
print(int(sum))

Submission status: Time Limit Exceeded

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

K = int(input())
ans = []
for i in range(1, K+1):
    for j in range(1, K+1):
        for k in range(1, K+1):
            ans.append(gcd(i, j, k))
print(sum(ans))

Submission status: Time Limit Exceeded

Solution code:
import fractions
import itertools

k=int(input())
tot=0
for l,m,n in itertools.product(range(1,k+1),range(1,k+1),range(1,k+1)):
    ans=l
    ans=fractions.gcd(ans,m)
    ans=fractions.gcd(ans,n)
    tot+=ans
print(tot)