Problem:


Score : 300 points

Problem Statement

Find \displaystyle{\sum_{a=1}^{K}\sum_{b=1}^{K}\sum_{c=1}^{K} \gcd(a,b,c)}.

Here \gcd(a,b,c) denotes the greatest common divisor of a, b, and c.

Constraints

1 \leq K \leq 200

K is an integer.

Input

Input is given from Standard Input in the following format:

K

Output

Print the value of \displaystyle{\sum_{a=1}^{K}\sum_{b=1}^{K}\sum_{c=1}^{K} \gcd(a,b,c)}.

Sample Input 1

2

Sample Output 1

9

\gcd(1,1,1)+\gcd(1,1,2)+\gcd(1,2,1)+\gcd(1,2,2)
+\gcd(2,1,1)+\gcd(2,1,2)+\gcd(2,2,1)+\gcd(2,2,2)
=1+1+1+1+1+1+1+2=9

Thus, the answer is 9.

Sample Input 2

200

Sample Output 2

10813692



Sample input:
2


Sample output:
9

Submission status: Accepted

Solution code:
import sys
import os
from io import BytesIO, IOBase

#########################
# imgur.com/Pkt7iIf.png #
#########################

# returns the list of prime numbers less than or equal to n:
'''def sieve(n):
    if n < 2: return list()
    prime = [True for _ in range(n + 1)]
    p = 3
    while p * p <= n:
        if prime[p]:
            for i in range(p * p, n + 1, p):
                prime[i] = False
        p += 2
    r = [2]
    for p in range(3, n + 1, 2):
        if prime[p]:
            r.append(p)
    return r'''

# returns all the divisors of a number n(takes an additional parameter start):
'''def divs(n, start=1):
    divisors = []
    for i in range(start, int(n**.5) + 1):
        if n % i == 0:
            if n / i == i:
                divisors.append(i)
            else:
                divisors.extend([i, n // i])
    return len(divisors)'''

# returns the number of factors of a given number if a primes list is given:
'''def divn(n, primes):
    divs_number = 1
    for i in primes:
        if n == 1:
            return divs_number
        t = 1
        while n % i == 0:
            t += 1
            n //= i
        divs_number *= t
    return divs_number'''

# returns the leftmost and rightmost positions of x in a given list d(if x isnot present then returns (-1,-1)):
'''def flin(d, x, default=-1):
    left = right = -1
    for i in range(len(d)):
        if d[i] == x:
            if left == -1: left = i
            right = i
    if left == -1:
        return (default, default)
    else:
        return (left, right)'''

#count xor of numbers from 1 to n:
'''def xor1_n(n):
    d={0:n,1:1,2:n+1,3:0}
    return d[n&3]'''

def cel(n, k): return n // k + (n % k != 0)
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return list(map(int, input().split()))
def lcm(a, b): return abs(a * b) // math.gcd(a, b)
def prr(a, sep=' '): print(sep.join(map(str, a)))
def dd(): return defaultdict(int)
def ddl(): return defaultdict(list)
def ddd(): return defaultdict(defaultdict(int))

# region fastio
 
BUFSIZE = 8192
 
 
class FastIO(IOBase):
	newlines = 0
 
	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = "x" in file.mode or "r" not in file.mode
		self.write = self.buffer.write if self.writable else None
 
	def read(self):
			while True:
					b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
					if not b:
							break
					ptr = self.buffer.tell()
					self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
			self.newlines = 0
			return self.buffer.read()
 
	def readline(self):
			while self.newlines == 0:
					b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
					self.newlines = b.count(b"\n") + (not b)
					ptr = self.buffer.tell()
					self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
			self.newlines -= 1
			return self.buffer.readline()
 
	def flush(self):
			if self.writable:
					os.write(self._fd, self.buffer.getvalue())
					self.buffer.truncate(0), self.buffer.seek(0)
 
 
class IOWrapper(IOBase):
	def __init__(self, file):
			self.buffer = FastIO(file)
			self.flush = self.buffer.flush
			self.writable = self.buffer.writable
			self.write = lambda s: self.buffer.write(s.encode("ascii"))
			self.read = lambda: self.buffer.read().decode("ascii")
			self.readline = lambda: self.buffer.readline().decode("ascii")
 

sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

from collections import defaultdict 
#from collections import deque
#from collections import OrderedDict
from math import gcd
#import time
#import itertools
#import timeit
#import random
#from bisect import bisect_left as bl
#from bisect import bisect_right as br
#from bisect import insort_left as il
#from bisect import insort_right as ir
#from heapq import *
#from queue import PriorityQueue
#mod=998244353
#mod=10**9+7
# for counting path pass prev as argument:
# for counting level of each node w.r.t to s pass lvl instead of prev:

k=ii()
ans=0
d2,d3=dd(),dd()
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: Accepted

Solution code:
import math

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

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

Solution code:
k = int(input())
d = [0]*(k+1)
for i in range(1, k+1):
    d[i] = pow(k//i, 3)

for i in reversed(range(1, k+1)):
    for j in range(2*i, k+1, i):
        d[i] -= d[j]

ans = 0
for i in range(1, k+1):
    ans += i*d[i]
print(ans)

Submission status: Accepted

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

import math

K = int(input())
ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
import numpy as np
 
K = INT()
sum = 0
 
for n in range(1, K+1):
  for m in range(1, K+1):
    sum1 = gcd(n, m)
    for l in range(1, K+1):
      sum += gcd(l, sum1)
 
print(sum)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
import numpy as np
 
K = INT()
sum = 0
 
for n in range(K):
  for m in range(K):
    sum1 = gcd(n+1, m+1)
    for l in range(K):
      sum += gcd(l+1, sum1)
 
print(sum)

Submission status: Accepted

Solution code:
from math import gcd
def INT(): return int(input())
 
 
K = INT()
sum = 0
 
for n in range(1, K+1):
  for m in range(1, K+1):
    for l in range(1, K+1):
      sum += gcd(gcd(n, m), l)
 
print(sum)

Submission status: Accepted

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

sum = 0
for i in range(1,K+1):
	for j in range(1,K+1):
		temp = math.gcd(i,j)
		for m in range(1,K+1):
			sum = sum + math.gcd(temp,m)

print(sum)

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

Submission status: Accepted

Solution code:
def gcd(x, y):
    while (y):
        x, y = y, x % y
    return x

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

Submission status: Accepted

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

sum = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        temp = math.gcd(i,j)
        for m in range(1,K+1):
            sum = sum+math.gcd(m,temp)
print(sum)

Submission status: Accepted

Solution code:
import math

K=int(input())
sum=0


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

print(sum)

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

Submission status: Accepted

Solution code:
n=int(input())
l=[]

def gcd(a,b):
  a,b=max(a,b),min(a,b)
  if a%b==0:
    return b
  else:
    return gcd(b,a%b)
  
for i in range(1,n+1):
  for j in range(1,n+1):
    l.append(gcd(i,j))
    
ans=0
for i in range(1,n+1):
  for j in l:
    ans+=gcd(i,j)
    
print(ans)

Submission status: Accepted

Solution code:
from os import path
if(path.exists('C:/Users/prana/Desktop/sublime/input.txt')):
    import sys
    sys.stdin = open("C:/Users/prana/Desktop/sublime/input.txt","r")
    sys.stdout = open("C:/Users/prana/Desktop/sublime/output.txt","w")

from math import gcd
def solve():
    ans = 0
    a = int(input()) 
    for i in range(a):
        for j in range(a):
            for k in range(a):
                ans += gcd(k+1,gcd(i+1,j+1))
    print(ans)

test_case = 1
while(test_case):
    solve()
    test_case -= 1

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):
        x = math.gcd(a,b)
        for c in range(1,K+1):
            sum+=math.gcd(x,c)
print(sum)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from math import gcd

n=int(input().strip())

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

Submission status: Accepted

Solution code:
def gcd(a,b):
##
#  if b == 0 :
#    return a
#  else:
#    return gcd(b,a % b)
##
  while b:
    a,b = b,a % b
  return a
###########################
N = int(input())
tmp = list()
s = 0

for i in range(1,N + 1):
  for j in range(1,N + 1):
      a = gcd(i,j)
      tmp.append(a)

for aTmp in tmp:
  for j in range(1,N + 1):
      a = gcd(aTmp,j)
      s += a

print(s)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

import math

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:

from math import gcd

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

print(result)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from math import gcd

K = int(input())
lst = []
for x in range(1, K + 1):
    for y in range(1, K + 1):
        for z in range(1, K + 1):
            lst.append(gcd(gcd(x, y), z))

print(sum(lst))

Submission status: Accepted

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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import math 

K = int(input())

def sol(K):
    res = 0
    for i in range(1, K+1):
        for j in range(1, K+1):
            t = math.gcd(i, j)
            for k in range(1, K+1):
                res += math.gcd(k, t)

    return res
  
print(sol(K))

Submission status: Accepted

Solution code:
import math

n = int(input())
answer = 0

for a in range(1,n+1):
    for b in range(1,n+1):
        t = math.gcd(a,b)
        for c in range(1,n+1):
            answer += math.gcd(t,c)
print(answer)

Submission status: Accepted

Solution code:
import math

k = int(input())
n = 0

for i in range(1,k+1):
    for j in range(1,k+1):
        a = math.gcd(i,j)
        for l in range(1,k+1):
            b = math.gcd(a,l)
            n += b

print(n)

Submission status: Accepted

Solution code:
#coding:utf-8

k = int(input())
count = 0

def gcd(a,b):
    if a >= b:
        k1, k2 = a, b
    elif a < b:
        k1, k2 = b, a

    r = k1 % k2
    if r != 0:
        return gcd(k2,r)
    elif r == 0:
        return k2

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

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

        f = gcd(a,b)

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

            g = gcd(f,c)
            
            if a == b and b != c:
                count += g * 3
            elif b == c and c != a:
                count += g * 3
            elif c == a and a != b:
                count += g * 3
            elif a == b and b == c:
                count += g
            else:
                count += g * 6

print("{}".format(count))

Submission status: Accepted

Solution code:
import math
from functools import reduce

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

Submission status: Accepted

Solution code:
K = int(input())
S = 0

def gcd(a,b):
   while b != 0:
       a, b = b, a % b
       if b ==0:
           return a
A1 = [0,0]
A2 = [0,0,0]
for i in range(1, K+1):
    S = S + i

if K > 1:
    for j in range(1, K):
        A1[0] =  j
        for k in range(j+1,K+1):
            A1[1] = k
            S += 6 * gcd(A1[1],A1[0])

if K > 2:
    for i1 in range(1, K-1):
        A2[0] = i1
        for k1 in range(i1+1, K):
            A2[1] = k1
            for j1 in range(k1+1,K+1):
                A2[2] = j1
                G3 = gcd(A2[2],A2[1])
                if G3 >= A2[0]:
                    S += 6 * gcd(G3,A2[0])
                else:
                    S += 6 * gcd(A2[0],G3)
print(S)

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

Solution code:
K = int(input())

table_gcd = [[0 for i in range(K)] for j in range(K)]
table_num = [0 for i in range(K)]

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

for a in range(0, K) :
  for b in range(0, a+1) :
    if(a == b) :
      table_gcd[a][b] = a+1
      table_gcd[b][a] = a+1
      table_num[a] += 1
    else :
      cd = gcd(a+1, b+1)
      table_gcd[a][b] = cd
      table_gcd[b][a] = cd
      table_num[cd-1] += 2
    
ans = 0
for c in range(0, K) :
  for cd in range(0, K) :
    ans += table_num[cd] * table_gcd[c][cd]
  
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):
        ab = gcd(a, b)
        for c in range(1, K+1):
            ans += gcd(ab, c)
print(ans)

Submission status: Accepted

Solution code:
from math import gcd

k = int(input())

n = 0

for i in range(1, k + 1):
    for i2 in range(1, k + 1):
        for i3 in range(1, k + 1):
            n += gcd(gcd(i, i2), i3)

print(n)

Submission status: Accepted

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
k=int(input())
def gcd(a,b):
  while b:
    a,b=b,a%b
  return a
def ggcd(a,b,c):
  return gcd(gcd(a,b),c)
ans=0
for a in range(k):
  for b in range(k):
    for c in range(k):
      ans+=ggcd(a+1,b+1,c+1)
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 i in range(1, K+1):
    for j in range(i+1, K+1):
        for k in range(j+1, K+1):
            sum += 6*gcd(i, j, k)
for i in range(1, K+1):
    for j in range(i+1, K+1):
        sum += 2*3*gcd(i, j)
sum += int( (K+1)*K/2 )
print(sum)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
MAX_K: int = 200

gt = [[0 for _ in range(MAX_K + 1)] for _ in range(MAX_K + 1)]

def gcd(x: int, y: int) -> int:
    if gt[x][y] > 0:
        return gt[x][y]
    ret: int = 0
    if x < y:
        ret = gcd(y, x)
    elif y == 0:
        ret = x
    elif y == 1:
        ret = 1
    else:
        ret = gcd(y, x % y)
    gt[x][y] = ret
    # print(f"gcd({x}, {y}) = {ret}")
    return ret

k = int(input())
print(sum([gcd(gcd(i + 1, j + 1), l + 1) for i in range(k) for j in range(k) for l in range(k)]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from math import gcd
def gc(a,b,c):
    return gcd(gcd(a,b),c)
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):
            x=gc(a,b,c)
            if a!=b and b!=c and c!=a:
                ans+=6*x
            elif a==b and b==c:
                ans+=x
            else:
                ans+=3*x
print(ans)

Submission status: Accepted

Solution code:
import math

input_num = int(input())
total = 0


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


for i in range(input_num):
    for j in range(input_num):
        for k in range(input_num):
            total += gcd(i + 1, j + 1, k + 1)
print(total)

Submission status: Accepted

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

Submission status: Accepted

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

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

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

print(sum)

Submission status: Accepted

Solution code:
K = int(input())

def ca(a,b):
    if a == 1:
        return 1
    while True:
        if a == 1:
            return 1
        if a == 0:
            return b
        t = a
        a = b %a
        b = t
    return b

def cal(a,b,c):
    mo = ca(a,b)
    ans = ca(mo,c)
    return ans


ans = 0
for a in range(1,K-1):
    ans += a
    ans += 6*cal(a,a,K)
    for b in range(a+1,K):
        ans += 6*cal(a,b,b)
        for c in range(b+1,K+1):
            ans += 6*cal(a,b,c)
    
ans += K + K-1 +6
if K == 1:
    print(1)
elif K == 2:
    print('9')
else:

    print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np

N=int(input())
count = 0

for i in range(1,N+1):
    i_ins=[]
    for x in range(1,i+1):
        if i//x != 0 and i%x == 0:
            i_ins.append(x)
    for j in range(1,N+1):
        i_j_ins=[]
        for y in i_ins:
            if j//y != 0 and j%y == 0:
                i_j_ins.append(y)
        if i_j_ins[-1]==1:
            #            print(i,j,i_j_ins[-1])
            count = count + i_j_ins[-1]*N
        else:
            for k in range(1,N+1):
                i_j_k_ins=[]
                for z in reversed(i_j_ins):
                    if k//z != 0 and k%z == 0:
                        i_j_k_ins.append(z)
                        break
            #    print(i,j,k,i_j_k_ins[-1])
                count = count + i_j_k_ins[-1]

print(count)

Submission status: Accepted

Solution code:
import math
from functools import reduce

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

print(sum)

Submission status: Accepted

Solution code:
import math
ans = 0

K = int(input())

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

print(ans)

Submission status: Accepted

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

K = int(input())

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

print(ans)

Submission status: Accepted

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

#ユーグリッド互除法（再起）
def gcd(p, q):
  # ユーグリッド互除法
  if (p%q==0):
    return q
  else:
    return gcd(q, p%q)

ans = 0

for abc in itertools.combinations_with_replacement([i+1 for i in range(K)], 3):
  a,b,c = abc
  gcd_ab = gcd(a, b)
  gcd_abc = gcd(gcd_ab, c)

  # 組み合わせ数を補整する
  if a == b == c:
    ans += gcd_abc
  elif a==b or b==c or a==c:
    ans += gcd_abc*3
  else:
    ans += gcd_abc * 6

print(ans)

Submission status: Accepted

Solution code:
import math

def main():

    k = int(input())
    
    r = range(1,k+1)

    #because gcd can only appear in this range
    count = [0]*201
    
    for i in r:
        for j in r:
            count[math.gcd(i,j)] += 1
    
    final = 0
    
    for i in range(1,201):
        if count[i] > 0:
            for j in r:
                final += count[i]*math.gcd(i,j)
    
    print(final)


main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from functools import reduce 
import math
import itertools

def gcd(numbers):
    return reduce(lambda x,y: math.gcd(x,y),numbers)

def comb(K):
    return itertools.combinations_with_replacement(range(1,K+1),3)

def main():
    k = int(input())
    if k == 1:
        print(1)
        return
    elif k == 2:
        print(9)
        return

    final = 0
    comb_list = list(comb(k))

    for i in comb_list:
        if len(set(i)) == 1:
            final += 1*gcd(i)
        elif len(set(i)) == 2:
            final += 3*gcd(i)
        else:
            final += math.factorial(3)*gcd(i)

    #print(comb_list)
    print(final)
main()

Submission status: Accepted

Solution code:
import math


k = int(input())
answer = 0
for w_a in range(1, k + 1):
    for w_b in range(1, k + 1):
        w = math.gcd(w_a, w_b)
        for w_c in range(1, k + 1):
            answer += math.gcd(w, w_c)

print(answer)

Submission status: Accepted

Solution code:
from functools import lru_cache

@lru_cache(maxsize=100000)
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def resolve():
    k = int(input())
    l = [None] * k ** 2
    for i in range(k):
        for j in range(k):
            l[i * k + j] = gcd(i + 1, j + 1)
    ans = 0
    for i in l:
        for j in range(k):
            ans += gcd(i, j + 1)
    print(ans)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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


def resolve():
    k = int(input())
    l = [None] * k ** 2
    for i in range(k):
        for j in range(k):
            l[i * k + j] = gcd(i + 1, j + 1)
    ans = 0
    for i in l:
        for j in range(k):
            ans += gcd(i, j + 1)
    print(ans)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import itertools
k=int(input())
def solve(a,b):
	if a<b:
		if b%a==0:
			return a
		else:
			return solve(a,b%a)
	if a%b==0:
		return b
	else:
		return solve(b,a%b)
arr=[i+1 for i in range(k)]
l=list(itertools.combinations_with_replacement(arr,3))
#l = [p for p in itertools.product(arr, repeat=3)]
s=0
dic={}

for i in l:
	a,b,c=i
	if a==b and a==c:
		s+=solve(c,solve(a,b))
	elif a==b or b==c or a==c:
		s+=3*(solve(c,solve(a,b)))
	else:
		s+=6*(solve(c,solve(a,b)))
print(s)

Submission status: Accepted

Solution code:
from math import gcd
#1≦k≦2*10^2
k = int(input())

ans = 0
#O(n^3)
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            ans += gcd(a, gcd(b, c))    #O((logn)^2)

print(ans)

Submission status: Accepted

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

for i in range(1,201):
    gcdtemp=[0]
    for j in range(1,201):
        gcdtemp.append(gcd(i,j))
    gcdcal.append(gcdtemp)

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+=gcdcal[gcdcal[i][j]][l]
print(sum)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import combinations as c
from math import gcd

n = int(input())+1

def f(n):
  res = 0
  for x, y, z in c(range(1, n), 3):
    res += gcd(x, gcd(y, z))
  res *= 6
  res += sum(range(1,n))
  for x, y in c(range(1, n), 2):
    res += 6*gcd(x, y)
  return res
print(f(n))

Submission status: Accepted

Solution code:
import math
from functools import reduce

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

x=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):
      x+=gcd(i,j,l)

print(x)

Submission status: Accepted

Solution code:
import math
from functools import reduce

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

x=0
k=int(input())
r = range(1, k + 1)
x = sum([gcd(a, b, c) for a in r for b in r for c in r])
print(x)

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
from collections import defaultdict
ml=lambda:map(int,input().split())
ll=lambda:list(map(int,input().split()))
ii=lambda:int(input())
ip=lambda:input()

"""========main code==============="""

t=ii()
ans=0
for i in range(1,t+1):
    for j in range(1,t+1):
        for k in range(1,t+1):
            ans+=math.gcd(math.gcd(i,j),k)
print(ans)

Submission status: Accepted

Solution code:
import sys
from math import gcd

sys.setrecursionlimit(10 ** 6)


def input(): return sys.stdin.readline().rstrip()


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

Submission status: Accepted

Solution code:
import math
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: Accepted

Solution code:
from math 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: Accepted

Solution code:
from math import gcd

K = int(input())
#K = 200
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: Accepted

Solution code:
from math import gcd
k = int(input())
t = 0
for i1 in range(1, k+1):
    for i2 in range(1, k+1):
        for i3 in range(1, k+1):
            t+=gcd(gcd(i1, i2), i3)
print(t)

Submission status: Accepted

Solution code:
from math import gcd
k = int(input())
ans = 0
t = 0
for i1 in range(1, k+1):
    for i2 in range(1, k+1):
        for i3 in range(1, k+1):
            t += gcd(gcd(i1, i2), i3)
print(t)

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

print(ans)