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:
import itertools
import math
import fractions
import functools
k = int(input())
h_list = []


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

sum = 0
for i in range(len(h_list)):
    a = fractions.gcd(h_list[i][0], h_list[i][1])
    sum += fractions.gcd(a,h_list[i][2])

print(sum)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import math
import fractions
import functools
k = int(input())
h_list = []



def gcd(numbers):
    return functools.reduce(fractions.gcd, numbers)

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

sum = 0
for i in range(len(h_list)):
    sum += gcd(h_list[i])

print(sum)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import math
import fractions
import functools
k = int(input())
h_list = []



def gcd(numbers):
    return functools.reduce(fractions.gcd, numbers)

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

sum = 0
for i in range(len(h_list)):
    sum += gcd(h_list[i])

print(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())
suma = 0

for i in range(1, k+1):
    for j in range(1, k+1):
        for l in range(1, k + 1):
            suma = gcd(i, j, l) + suma


print(suma)

Submission status: Time Limit Exceeded

Solution code:
import math
k = int(input())
a = list(range(1,k+1))
ans = 0
for x in a:
  for y in a:
    for z in a:
      ans += math.gcd(math.gcd(x,y),z)
print(ans)

Submission status: Time Limit Exceeded

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


k = int(input())
ans = 0
for i in range(1, k + 1):
    for j in range(1, k + 1):
        tgcd = gcd(i, j)
        for k in range(1, k + 1):
            l = gcd(tgcd, k)
            ans += l

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

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

Submission status: Time Limit Exceeded

Solution code:
import math

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def gcd(p, q):
    r = 0
    while q > 0:
        r = p % q
        p = q
        q = r
    return p

if __name__ == "__main__":
    K = int(input())
    total = 0
    for a in range(1, K+1):
        for b in range(1, K+1):
            for c in range(1, K+1):
                total += gcd(a, gcd(b, c))
    print(total)

Submission status: Time Limit Exceeded

Solution code:
def gcd(p, q):
    while q > 0:
        r = p % q
        p = q
        q = r
    return p

if __name__ == "__main__":
    K = int(input())
    total = 0
    for a in range(1, K+1):
        for b in range(1, K+1):
            for c in range(1, K+1):
                total += gcd(a, gcd(b, c))
    print(total)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce

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

print(sum)

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce
K=int(input())

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

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

Submission status: Time Limit Exceeded

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

from fractions import gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
from bisect import bisect_left, bisect_right, bisect, insort_left, insort_right, insort
from itertools import accumulate, product, permutations, combinations, combinations_with_replacement

K = int(input())

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

Submission status: Time Limit Exceeded

Solution code:
K = int(input())


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


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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
K = int(input())
bc = []


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


fin = 0
for a in range(K):
    bc = []
    for b in range(K):
        for c in range(K):
            ans = gcd(b+1, c+1)
            bc.append(ans)
    fin += sum([gcd(a+1, i) for i in bc])

print(fin)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

def gcd(p, q):
  if p % q == 0:
    return q
  return gcd(q, p % q)

ans = 0
for x in range(1,N+1):
  for y in range(1,N+1):
    for z in range(1,N+1):
      ans += gcd(gcd(x, y), z)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf
# @pysnooper.snoop()
#import pysnooper # debug
from functools import lru_cache

import math
#from sortedcontainers import SortedList, SortedDict, SortedSet # no in atcoder
import bisect

def mutual_division_method(a, b):
    while not (a == 0 or b == 0):
        if a < b:
            b = b % a
        else:
            a = a % b
    if a == 0:
        return b
    else:
        return a



def gcd(a, b, c):
    #print('a, b, c', a, b, c) # debug
    d = mutual_division_method(a, b)
    e = mutual_division_method(d, c)
    #print('e', e) # debug
    return e

if __name__ == '__main__':
    k = int(input())
    s = 0
    for a in range(1, k + 1):
        for b in range(1, k + 1):
            for c in range(1, k + 1):
                l = a, b, c
                sorted(l)
                ans = gcd(*l)
                s += ans
    #print('s') # debug
    print(s)

    #print('\33[32m' + 'end' + '\033[0m') # debug

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf
# @pysnooper.snoop()
#import pysnooper # debug
from functools import lru_cache

import math
#from sortedcontainers import SortedList, SortedDict, SortedSet # no in atcoder
import bisect

@lru_cache(maxsize=None)
def mutual_division_method(a, b):
    while not (a == 0 or b == 0):
        if a > b:
            a = a % b
        else:
            b = b % a
    if a == 0:
        return b
    else:
        return a

def mdm(a, b):
    if a < b:
        b, a = a, b
    return mutual_division_method(a, b)


def gcd(a, b, c):
    #print('a, b, c', a, b, c) # debug
    d = mdm(a, b)
    e = mdm(d, c)
    #print('e', e) # debug
    return e

if __name__ == '__main__':
    k = int(input())
    s = 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)
                s += ans
    #print('s') # debug
    print(s)

    #print('\33[32m' + 'end' + '\033[0m') # debug

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def gcd(a,b):
    if a>b:
        r=a%b
        if r==0:
            return b
        return gcd(b,r)
    elif a<b:
        r=b%a
        if r==0:
            return a
        return gcd(a,b%a)
    else:
        return a
k=int(input())
sum=0
for i in range(1,k+1):
    for j in range(1,k+1):
        for l in range(1,k+1):
            sum+=gcd(i,gcd(j,l))
print(sum)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

k = int(input())
sum = 0

for i in range(k):
    i = i+1
    for j in range(k):
        j = j+1
        for l in range(k):
            l = l+1
            if(i == j and j == l):
                sum += gcd(gcd(i,j),l)
            elif(i == j and j < l):
                sum += gcd(gcd(i,j),l) * 3
            elif(i == j and j > l):
                sum += gcd(gcd(i,j),l) * 3
            elif(i < j and j < l):
                sum += gcd(gcd(i,j),l) * 6

print(sum)

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
from functools import reduce

def solve():
    K = int(input())
    ans = 0

    for i in range(1,K+1):
        num = [0, 0, 0]
        num[0] = i
        for k in range(1,K+1):
            num[1] = k
            for m in range(1,K+1):
                num[2] = m
                ans += reduce(gcd, num)
    return ans

print(solve())

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from math import gcd

K = int(input())
l = [0 for i in range(K**3)]

ans = 0

for i in range(1,K+1):
    num = [0, 0, 0]
    num[0] = i
    for k in range(1,K+1):
        num[1] = k
        for m in range(1,K+1):
            num[2] = m
            ans += reduce(gcd, num)


print(ans)

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
import math
from functools import reduce
def gcd_list(*numbers):#引数はリスト
    return reduce(math.gcd, numbers)
ans=n**2
for i in range(2,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            ans+=gcd_list(i,j,k)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
import math
from functools import reduce
def gcd_list(*numbers):#引数はリスト
    return reduce(math.gcd, numbers)
ans=n**2
for i in range(2,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            l=[i,j,k]
            ans+=gcd_list(*l)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
import math
from functools import reduce
def gcd_list(*numbers):#引数はリスト
    return reduce(math.gcd, numbers)
ans=0  
for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            l=[i,j,k]
            ans+=gcd_list(*l)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

K = int(input())

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

print(total)

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce

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

k = int(input()) + 1
counter = 1 + (k-2) * 3 + (k-2) * (k-2) * 3
for p in range(2, k):
  for q in range(2, k):
    for r in range(2, k):
      counter += gcd(p, q, r)
print(counter)

Submission status: Time Limit Exceeded

Solution code:
import sys
import os
import bisect, collections, copy, itertools, math, string
from functools import reduce
def I(): return int(input())
def S(): return input()
def LI(): return list(map(int, input().split()))
def LS(): return list(input().split())

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


def solve():
	K = I()

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

if __name__ == '__main__':
	solve()

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 c in range(1,k+1):
    for b in range(1,k+1):
        for a in range(1,k+1):
            # res += gcd(a,b,c)
            gcd1 = math.gcd(a,b)
            gcd2 = math.gcd(gcd1,c)
            res += gcd2
print(res)

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

Submission status: Time Limit Exceeded

Solution code:
from math import gcd
counter = 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):
            d = gcd(a,b)
            counter += gcd(c,d)


print(counter)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import math
 
K = int(input())
 
def gcd(a, b, c):
    g = math.gcd(a, b)
    return math.gcd(g, c)
 
result = sum((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(result)

Submission status: Time Limit Exceeded

Solution code:

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

k = int(input())
ans = 0
mem = [[0 for a in range(k+1)]for b in range(k+1)]
n = k+1
for i in range(1,n):
    for j in range(1,n):
        for k in range(1,n):
            ans += gcd(gcd(i,j),k)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
K=int(input())

Ans=0
import math

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

print(Ans)

Submission status: Time Limit Exceeded

Solution code:

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

k = int(input())
ans = 0
mem = [[[0 for a in range(k+1)]for b in range(k+1)] for c in range(k+1)]
n = k+1
for i in range(1,n):
    for j in range(1,n):
        for k in range(1,n):
            a = max([i,j,k])
            b = min([i,j,k])
            c = sum([i,j,k]) - a - b
            if mem[a][b][c]:
                ans += mem[a][b][c]
            else:
                d = gcd(gcd(k,j),i)
                ans += d
                mem[a][b][c] = d
            # print("aaaaaa",i,j,k,ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
K = int(input())
def gcd(i, j):
  if i<j:
    tmp=i
    i=j
    j=tmp
  if i%j==0:
    return j
  else:
    return gcd(j, i%j)
count = 0
for i in range(1, K+1):
  for j in range(1, K+1):
    x=gcd(i, j)
    for k in range(1, K+1):
      count += gcd(x, k)
print(count)

Submission status: Time Limit Exceeded

Solution code:
K = int(input())
def gcd(i, j):
  if i%j==0:
    return j
  else:
    return gcd(j, i%j)
count = 0
for i in range(1, K+1):
  for j in range(1, K+1):
    x=gcd(i, j)
    for k in range(1, K+1):
      _gcd=gcd(x, k)
      count += _gcd
print(count)

Submission status: Time Limit Exceeded

Solution code:
K = int(input())
import math
def gcd(i, j):
  if i<j:
    tmp=i
    i=j
    j=tmp
  if i%j==0:
    return j
  else:
    return gcd(j, i%j)
count = 0
for i in range(1, K+1):
  for j in range(1, K+1):
    x=gcd(i, j)
    for k in range(1, K+1):
      _gcd=gcd(x, k)
      count += _gcd
print(count)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import math
k = int(input())
ans = 0
x = 10**9 + 7
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)
            ans = ans % x
print(ans)

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:
def gcd(a,b):
  if a%b==0:
    return b
  return gcd(b,a%b)

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(gcd(a,b),c)
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())
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:
# -*- coding: utf-8 -*-

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


K = int(input())
x=0
for i in range(K):
    for j in range(K):
        g1=gcd(i+1,j+1)
        for k in range(K):
            g2=gcd(g1,k+1)
            x=x+g2
            #print("{}".format(g))
print("{}".format(x))

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd

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

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

    print(t)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import fractions

n = int(input())

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

print(t)

Submission status: Time Limit Exceeded

Solution code:
import fractions

n = int(input())

nums = []
for i in range(1, n+1):
    for j in range(1, n+1):
        for k in range(1, n+1):
            nums.append([i, j, k])

t = 0
for num in nums:
    ans = num[0]
    for i in range(1, 3):
        ans = fractions.gcd(ans, num[i])
    t += ans

print(t)

Submission status: Time Limit Exceeded

Solution code:
def gcd(p, q) :
	if p % q == 0 :
		return q
	else :
		return gcd(q,p%q)
if __name__ == '__main__':
	ans = 0
	tmp = 0
	k = int(input())
	for i in range(1,k+1) :
		for j in range(1, k+1) :
			tmp = gcd(i,j)
			for l in range(1, k+1) :
				ans += gcd(tmp,l)
	print(ans)

Submission status: Time Limit Exceeded

Solution code:
def gcd(p, q) :
	if p % q == 0 :
		return q
	else :
		return gcd(q,p%q)
if __name__ == '__main__':
	ans = 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) :
				ans += gcd(gcd(i,j),l)
	print(ans)

Submission status: Time Limit Exceeded

Solution code:
#ABC162c
import math
from functools import reduce

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

k = int(input())
abc = 0

for i in range(1,k+1):
    for i2 in range(1,k+1):
        ab = gcd(i,i2)
        for i3 in range(1,k+1):
            abc += gcd(ab, i3)
print(abc)

Submission status: Time Limit Exceeded

Solution code:
k = int(input())
def gcd2(x,y):
    if y == 0:
        return x
    else:
        return gcd2(y,x%y)
def gcd(x,y,z):
    return gcd2(gcd2(x,y),z)
sum = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        for l in range(1,k+1):
            sum = sum + gcd(i,j,l)
print(sum)

Submission status: Time Limit Exceeded

Solution code:
#ABC162c
import math
from functools import reduce

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

k = int(input())
abc = 0
for i in range(k):
    for i2 in range(k):
        for i3 in range(k):
            abc += gcd(i+1, i2+1, i3+1)
print(abc)

Submission status: Time Limit Exceeded

Solution code:
def gcd(x1,x2):
    r=0
    while True:
        if x1==x2:
            r=x1
            break
        elif x1<x2:
            x2=x2-x1
        else:
            x1=x1-x2
    return r

x = int(input())

ans=0

for a in range(1,x+1):
    for b in range(1,a+1):
        for c in range(1,b+1):
            gcd1=gcd(a,b)
            gcd2=gcd(gcd1,c)
            if a==b and b==c:
                ans += gcd2
            elif a==b or b==c or c==a:
                ans += 3*gcd2
            else:
                ans += 6*gcd2

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

x = int(input())

ans=0

for a in range(1,x+1):
    for b in range(a,x+1):
        for c in range(b,x+1):
            if a==b and b==c:
                ans += np.gcd.reduce([a,b,c])
            elif a==b or b==c or c==a:
                ans += 3*np.gcd.reduce([a,b,c])
            else:
                ans += 6*np.gcd.reduce([a,b,c])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    k = int(input())
    ans = 0
    for i in range(1,k+1):
        for j in range(1,k+1):
            for k in range(1,k+1):
                ans += gcd(gcd(i,j),k)

    print(ans)

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
k = int(input())
k = [int(x)+1 for x in range(k)]
#print(k)
from fractions import gcd
from itertools import product,combinations
from functools import reduce
num = 0

for v in product(k,repeat =3):
    v = (list(v))
    
    a = reduce(gcd,v)
    num +=a
    #print(v,num)
print(num)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial
import fractions as fr

from sys import stdin


def main():
    k = int(stdin.readline())

    ans = 0

    for a in range(1, k + 1):
        for b in range(a, k + 1):
            d = fr.gcd(a, b)
            for c in range(b, k + 1):
                e = fr.gcd(d, c)
                ans += e * factorial(3)//factorial(3 - len(set([a, b, c])) + 1)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import fractions as fr

from sys import stdin


def main():
    k = int(stdin.readline())

    g = [[[0 for _ in range(k)] for _ in range(k)] for _ in range(k)]

    for a in range(1, k + 1):
        for b in range(a, k + 1):
            g[a - 1][b - 1][0] = fr.gcd(a, b)
            for c in range(b, k + 1):
                g[a - 1][b - 1][c - 1] = fr.gcd(g[a - 1][b - 1][0], c)

    ans = 0

    for a in range(k):
        for b in range(k):
            for c in range(k):
                abc = sorted([a, b, c])
                ans += g[abc[0]][abc[1]][abc[2]]

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
K=int(input())
count=0
import math
for a in range(1,K+1):
  for b in range(1,K+1):
    for c in range(1,K+1):
      count+=math.gcd(math.gcd(a,b),c)#c内でいちいちmath.gcd(a,b)を計算してしまっている。
print(count)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import os
import fractions
import itertools

def file_input():
    f = open('Beginner_Contest_162/input.txt', 'r')
    sys.stdin = f

def main():
    #file_input()
    K=int(input())
    # map(int, input().split())
    sum=0

    combi_l = itertools.combinations_with_replacement(range(1,K+1),3)
    # print(combi_l)

    for combi in combi_l:
        # print(combi)
        if combi[0]==combi[1]==combi[2]:
            sum+=fractions.gcd(fractions.gcd(combi[0],combi[1]),combi[2])
        elif combi[0]==combi[1] or combi[1]==combi[2] or combi[2]==combi[0]:
            sum+=3*fractions.gcd(fractions.gcd(combi[0],combi[1]),combi[2])
        else:
            sum+=6*fractions.gcd(fractions.gcd(combi[0],combi[1]),combi[2])

    # for a in range(1,K+1):
    #     for b in range(1,K+1):
    #         tmp=fractions.gcd(a,b)
    #         for c in range(1,K+1):
    #             sum+=fractions.gcd(tmp,c)

    print(sum)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import os
import fractions

def file_input():
    f = open('Beginner_Contest_162/input.txt', 'r')
    sys.stdin = f

def main():
    #file_input()
    K=int(input())
    # map(int, input().split())
    sum=0

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

    print(sum)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
k = int(input())
s = 0
a = []
b = []
for i in range(1,k+1):
    for j in range(1,k+1):
        for l in range(1,k+1):
            p = [i,j,l]
            p.sort()
            if (p in a):
                s += b[a.index(p)]
            else:
                a.append(p)
                t = math.gcd(i,j)
                q = math.gcd(t,l)
                s += q
                b.append(q)
print(s)

Submission status: Time Limit Exceeded

Solution code:
import math
#import itertools
num = (int)(input())
total = 0
#for i, j, k in itertools.product(list(range(1, num + 1)), list(range(1, num + 1)), list(range(1, num + 1))):
#  total += math.gcd(math.gcd(i, j), k)
#print(total)
for i in range(1, num + 1):
  for j in range(1, num + 1):
    for k in range(1, num + 1):
      total += math.gcd(math.gcd(i, j), k)
print(total)

Submission status: Time Limit Exceeded

Solution code:
k = int(input())
import math
from functools import reduce

l = []
def gcd(*numbers):
    return reduce(math.gcd, numbers)
def gcd_list(numbers):
    return reduce(math.gcd, numbers)

for i in range(1, k+1):
    for j in range(1, k+1):
        for m in range(1, k+1):
            n = gcd(i, j, m)
            l.append(n)
print(sum(l))

Submission status: Time Limit Exceeded

Solution code:
K = int(input())

#a,bの最大公約数
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

Solution code:
K = int(input())

import math
from functools import reduce

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

S = 0

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
import functools

def euclid(a, b):
    if b == 0:
        return a
    else:
        return euclid(b, a%b)
def gcd(nums):
    return functools.reduce(euclid, nums)

k = int(input())
ans = 0
for v in itertools.combinations_with_replacement([i+1 for i in range(k)], 3):
    if len(set(v)) == 1:
        ans = ans + gcd(v) * 1
    elif len(set(v)) == 2:
        ans = ans + gcd(v) * 3
    elif len(set(v)) == 3 :
        ans = ans + gcd(v) * 6
print(ans)

Submission status: Time Limit Exceeded

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

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:
sum=0
K=int(input())+1
r=1
for a in range(1,K):
  for b in range(1,K):
    p=a
    q=b
    if p%q==0:
      r=q
    while p%q!=0:
      r=p%q
      p=q
      q=r
    ab=r
    for c in range(1,K):
      p=c
      q=ab
      if p%q==0:
        r=q
      while p%q!=0:
        r=p%q
        p=q
        q=r
      sum+=r
print(sum)

Submission status: Time Limit Exceeded

Solution code:
sum=0
K=int(input())+1
r=1
for a in range(1,K):
  for b in range(1,K):
    for c in range(1,K):
      p=a
      q=b
      if p%q==0:
        r=q
      while p%q!=0:
        r=p%q
        p=q
        q=r
      
      p=r
      q=c
      if p%q==0:
        r=q
      while p%q!=0:
        r=p%q
        p=q
        q=r
      sum+=r
print(sum)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

import numpy as np


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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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


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


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