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

Solution (Python):
import math

n = int(input())
sum = (n - 1) * (n - 1) + n * n + n * (n - 1)
for i in range(2, n + 1):
    for j in range(i, n + 1):
        for k in range(j, n + 1):
            otv = math.gcd(math.gcd(i, j), k)
            if i != j and j != k:
                otv *= 6
            elif i != j or j != k:
                otv *= 3
            sum += otv
print(sum)

Solution (Python):
from math import gcd
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)

Solution (Python):
from math import gcd
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)

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

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

Solution (Python):
import math
from functools import reduce
from sys import stdin
import itertools

def gcd(*numbers):
    return reduce(math.gcd, numbers)
  
def main():
  N = int(stdin.readline())
  N_list = list(range(1, N+1))
  
  ans = 0
  
  for xs in itertools.combinations_with_replacement(N_list, 3):
    if len(set(xs)) == 1:
      ans += gcd(xs[0], xs[1], xs[2])
    elif len(set(xs)) == 2:
      ans += 3*gcd(xs[0], xs[1], xs[2])
    else:
      ans += 6*gcd(xs[0], xs[1], xs[2])
      
  print(ans)

if __name__ == '__main__':
  main()

Solution (Python):


import math

    
def main():
	num = int(input())
	sum = 0
	for i in range(num):
		a = i+1
		for j in range(num):
			b = j+1
			for k in range(num):
				c = k+1
				sum += math.gcd(math.gcd(a,b),c)
	print (sum)

if __name__ == '__main__':
	main()

Solution (Python):
k = int(input())
import itertools
def GCD(a,b):
    if(a%b == 0):
        return b
    else:
        return GCD(b,a%b)
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(GCD(a,b),c)
print(total)

Solution (Python):
import math
from functools import reduce

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

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

print(ans)

Solution (Python):

import math

n = int(input())+1
a = int(0)
for i in range(1, n):
  for j in range(1, n):
    b = math.gcd(i,j)
    for k in range(1, n):
      a = a + math.gcd(b,k)
print("{}".format(a))

Solution (Python):
k = int(input())
ans=0

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

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)

Solution (Python):
import math
A = int(input())
def gcd(A):
    total = 0
    for i in range(1,A+1):
        for j in range(1,A+1):
            B = math.gcd(i,j)
            for k in range(1,A+1):
                total += math.gcd(B,k)
    return total
print(gcd(A))

Solution (Python):
from math import gcd
ans=0
i = int(input())
for a in range(1,i+1):
  for b in range(1,i+1):
    for c in range(1,i+1):
      n=gcd(gcd(a,b),c)
      ans+=n
print(ans)

Solution (Python):
from collections import defaultdict, deque
import sys
import heapq
import bisect
import math
import itertools
import string
import queue
import copy
import time

from math import gcd

sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10 ** -7

def inp(): return int(sys.stdin.readline())
 
def inp_list(): return list(map(int, sys.stdin.readline().split()))

def lcm(x, y): return (x * y) // gcd(x, y)


K = inp()

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

dic = {} 
ans = 0
for i in range(1, K + 1):
    for j in range(i, K + 1):
        
        for k in range(j, K + 1):
            
            
            a = gcd_3(i, j, k)
            if i == j == k:
                ans += a
            elif i == j or j == k:
                ans += a * 3
            else:
                ans += a * 3 * 2
print(ans)

Solution (Python):
from collections import defaultdict, deque
import sys
import heapq
import bisect
import math
import itertools
import string
import queue
import copy
import time

from math import gcd

sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10 ** -7

def inp(): return int(sys.stdin.readline())
 
def inp_list(): return list(map(int, sys.stdin.readline().split()))

def lcm(x, y): return (x * y) // gcd(x, y)


K = inp()

dic = {} 
ans = 0
for i in range(1, K + 1):
    for j in range(i, K + 1):
        
        for k in range(j, K + 1):
            
            a = gcd(gcd(i, j), k)
            if i == j == k:
                ans += a
            elif i == j or j == k:
                ans += a * 3
            else:
                ans += a * 3 * 2
print(ans)

Solution (Python):
import math
from functools import reduce

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

k = int(input())

sum_count = 0
for i in range(1, k+1):
    a = i
    for j in range(1, k+1):
        b = j
        for l in range(1, k+1):
            c = l
            sum_count = sum_count + gcd(a,b,c)

print(sum_count)

Solution (Python):
K=int(input())
import math
ans=0
for a in range(1,K+1):
  for b in range(1,K+1):
    g=math.gcd(a,b)
    if g==1:
      ans += K
      continue
    for c in range(1,K+1):
      ans += math.gcd(g,c)
print(ans)

Solution (Python):
import math

n = int(input())

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

Solution (Python):
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)

Solution (Python):


def euclid(m,n):
    
    if m < n:
        m, n = n, m
    while n != 0:
        m, n = n, m % n
    return m


num = int(input('')) 
ans_sum = 0

for a in range(1,num+1):
    for b in range(1,num+1):
        gcd_ab = euclid(a,b)
        for c in range(1,num+1):
            ans_sum = ans_sum + euclid(gcd_ab,c)

ans_sum = ans_sum

print(ans_sum)

Solution (Python):
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):
            x = math.gcd(math.gcd(i, j), k)
            if i == j == k:
                ans += x
            elif i != j != k:
                ans += x * 6
            else:
                ans += x * 3

print(ans)

Solution (Python):
def gcd(a, b):
    if a < b:
        a, b = b, a
    return b if a % b == 0 else gcd(b, a%b)
def solve(k):
    ans = 0
    for a in range(1, k+1):
        for b in range(1, k+1):
            d = gcd(a, b)
            if d in [1,2,3,5,7,11,13]:
                num = k // d
                ans += num * d + (k - num)
            else:
                for c in range(1, k+1):
                    ans += gcd(c, d)
    return ans

k = int(input())
print(solve(k))

Solution (Python):
import math

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

Solution (Python):
import itertools
import math
K = [i for i in range(1, int(input()) + 1)]
numbers = itertools.combinations_with_replacement(K, 3)

sum_gcd = 0
for i in numbers:
    a = math.gcd(i[0], i[1])
    b = math.gcd(a, i[2])

    if i[0] != i[1] != i[2]:
        sum_gcd += b * 6
    elif i[0] == i[1] == i[2]:
        sum_gcd += b
    else:
        sum_gcd += b * 3

print(sum_gcd)

Solution (Python):
from math import gcd

K = int(input())
total = 0
for a in range(1, K + 1):
    for b in range(a, K + 1):
        d1 = gcd(a, b)
        for c in range(b, K + 1):
            d2 = gcd(d1, c)
            if a == b == c:
                total += d2
            elif a == b < c or a < b == c:
                total += d2 * 3
            elif a < b < c:
                total += d2 * 6
            else:
                assert False
print(total)

Solution (Python):
n=int(input())

total=0

for i in range(n):
  
  j=i
  while j<n:
    
    k=j
    while k<n:
      
      kouho=min(i+1,j+1,k+1)
      while True:
        
        if (i+1)%kouho==0 and (j+1)%kouho==0 and (k+1)%kouho==0:
          
          if i==j and j==k:
            total+=kouho
          
          elif i==j or j==k or k==i:
            total+=kouho*3
          
          else:
            total+=kouho*6
          break
        else:
          kouho -= 1
      k+=1
    j+=1
          
print(total)

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

Solution (Python):
import math


def main():
    k: longlong
    result: longlong

    k = int(input())

    result = 0

    for x in range(1, k + 1):
        for y in range(1, k + 1):
            for z in range(1, k + 1):
                temp = math.gcd(math.gcd(x, y), z)
                result += temp
    print(result)


if __name__ == "__main__":
    main()

Solution (Python):
import math 

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

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

Solution (Python):
import math
import itertools

K = int(input())
K = [i for i in range(1, K+1)]
p = itertools.combinations_with_replacement(K, 3)
p = list(p)
g = 0

for i in p:
    a = math.gcd(i[0], i[1])
    b = math.gcd(a, i[2])
    if i[0] != i[1] != i[2]:
        g += b*6
    elif i[0] == i[1] == i[2]:
        g += b
    else:
        g += b*3

print(g)

Solution (Python):
import math

K = int(input())
g = 0
for i in range(1, K+1):
    for j in range(1, i+1):
        for k in range(1, j+1):
            a = math.gcd(i, j)
            b = math.gcd(a, k)
            if i != j != k:
                g += b*6
            elif i == j == k:
                g += b
            else:
                g += b*3

print(g)

Solution (Python):

from math import gcd

N = int(input())
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)

Solution (Python):
import math
k = int(input())
ans = 0

for a in range(1, k+1):
    for b in range(1, a+1):
        for c in range(1, b+1):
            g_ab = math.gcd(a ,b)
            g_abc = math.gcd(g_ab, c)
            if a != b != c:
                ans += g_abc * 6
            elif a == b == c:
                ans += g_abc
            else:
                ans += g_abc * 3
print(ans)

Solution (Python):
import math
from functools import reduce

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

Solution (Python):
k, = (int(x) for x in input().split())
 
n = 3
c = {} 
t = 0
for x in range(k, 0, -1):
    c[x] = (k // x) ** n
    c[x] = c[x] - sum(c[x * y] for y in range(2, k // x + 1))
    s = c[x] * x
    t += s
    
 
print(t)

Solution (Python):
from math import gcd
from itertools import product
k = int(input())
res = 0
for a, b, c in product(range(1, k+1), range(1, k+1), range(1, k+1)):
    res += gcd(gcd(a, b), c)
print(res)

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

Solution (Python):
K = int(input())
total = 0

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

for a in range(K):
  for b in range(K):
    tmp = gdc(b+1, a+1)
    for c in range(K):
      total += gdc(c+1, tmp)
print(total)

Solution (Python):
from math import gcd
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(i,gcd(j,k))
print(ans)

Solution (Python):
def gdc(x,y):
  if x%y==0:
    return y
  return gdc(y, x%y)

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

  for a in range(K):
    for b in range(K):
      for c in range(K):
        total += gdc(c+1, gdc(b+1, a+1))
  print(total)
  
if __name__ == '__main__':
    main()

Solution (Python):
K = int(input())
total = 0

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

for a in range(K):
  for b in range(K):
    for c in range(K):
      total += gdc(c+1, gdc(b+1, a+1))
print(total)

Solution (Python):
from math import gcd
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)

Solution (Python):
from math import gcd

k = int(input())
l = [[[0] * (k + 1) for i in range(k + 1)] for j in range(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):
            mn, mx = min(a, b, c), max(a, b, c)
            mi = a + b + c - mn - mx
            if l[a][b][c]:
                ans += l[a][b][c]
                continue
            else:
                ans += gcd(gcd(a, b), c)
print(ans)

Solution (Python):


k = int(input())

c = [ 0 for i in range(k + 1) ]

for i in range(k, 0, -1):
    c[i] = (k // i) ** 3
    for j in range(2, k + 1):
        if i * j > k:
            break
        else:
            c[i] -= c[i * j]

s = 0
for i in range(1, k + 1):
    s += i * c[i]

print(s)

Solution (Python):
import math

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

Solution (Python):
k = int(input())
def gcd(p,q):
  if(p % q == 0):
    return q
  return gcd(q, p % q)
res = 0
for i in range(1, k+1):
  for j in range(1, k+1):
    for p in range(1, k+1):
      res = res + gcd(i,gcd(j,p))
print(res)

Solution (Python):
K = int(input())

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


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

s = 0
for i in range(1, K + 1):
  for j in range(1, K + 1):
    for k in range(1, K + 1):
      s += gcds[gcds[i][j]][k]

print(s)

Solution (Python):
K = int(input())

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


gcds = [[0 for _ in range(K + 1)] for _ in range(K + 1)]

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

s = 0
for i in range(1, K + 1):
  for j in range(1, K + 1):
    for k in range(1, K + 1):
      s += gcds[gcds[i][j]][k]

print(s)

Solution (Python):
from math import gcd
import numpy as np


def sum_gcd(k: int) -> int:
    
    sum_p1 = 0
    for h in range(1, k + 1):
        for i in range(1, h):
            for j in range(1, i):
                sum_p1 += gcd(gcd(h, i), j)
                
    
    sum_p2 = 0
    for h in range(1, k + 1):
        for i in range(1, h):
            sum_p2 += gcd(h, i)

    
    sum_p3 = k * (k + 1) //2

    answer = sum_p1 * 6 + sum_p2 * 6 + sum_p3
    
    return answer


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


if __name__ == '__main__':
    main()

Solution (Python):
def gcd(x,y,z):
    for i in range(x, 0, -1):
        if x%i==0 and y%i==0 and z%i==0:
            
            return i
            break
            
    

def main():
    import sys
    N = int(sys.stdin.readline())
    total=0
    for i in range(1, N+1):
        for j in range(i, N+1):
            for k in range(j, N+1):
                if i==j and j==k:
                    total +=gcd(i, j, k)
                elif i==j or j==k or i==k:
                    total +=gcd(i, j, k)*3
                else:
                    total +=gcd(i, j, k)*6
                
    print(total)
    


if __name__=='__main__':
    main()

Solution (Python):
import math
from typing import List, NoReturn


def sum_gcd(k: int) -> int:
    cache: List[List[List[int]]] = [[[0] * (k + 1) for i in range(k + 1)] for j in range(k + 1)]

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

        result: int = 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: int = 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() -> NoReturn:
    k: int = int(input().rstrip())
    print(sum_gcd(k))


if __name__ == '__main__':
    main()

Solution (Python):


import sys
from math import gcd
INT_MAX = sys.maxsize
INT_MIN = -(sys.maxsize)
sys.setrecursionlimit(10**7)
mod = 1000000007


def IOE():
    sys.stdin = open("input.txt", "r")
    sys.stdout = open("output.txt", "w")


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


def main():
    n = int(sys.stdin.readline())
    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(i, j, k)
    print(ans)


if __name__ == "__main__":
    try:
        IOE()
    except:
        pass
    main()

Solution (Python):
def gcd(a,b):
	i = a
	j = b
	while i!=j:
		if i > j:
			i = i-j
		else :
			j = j - i
	return i

k = int(input())

ret = 0
for i in range(1,k+1):
	for j in range(i,k+1):
		for l in range(j,k+1):
			g = gcd(i,gcd(j,l))
			if (i == j) and (j == l):
				m = 1
			elif (i == j) or (j == l) or (l == i):
				m = 3
			else :
				m = 6
			
			ret += g*m
print(ret)

Solution (Python):
def gcd(a, b):
    if a%b==0: return b
    return gcd(b, a%b)
K=int(input())
sum=0
for a in range(1,K+1):
    for b in range(a,K+1):
        for c in range(b,K+1):
            if a==b==c: sum+=a
            elif a!=b!=c: sum+=gcd(gcd(a,b),c)*6 
            else: sum+=gcd(gcd(a,b),c)*3
print(sum)

Solution (Python):
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)

Solution (Python):
import math
from functools import reduce
from itertools import product
 
x = int(input())
 
s = 0
for i in product(range(1, x+1), repeat=3):
  s += reduce(math.gcd, i)
print(s)

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

Solution (Python):
import math
  
def main():
  k=int(input())
  cur=0
  for a in range(1,k+1):
    for b in range(1,k+1):
      for c in range(1,k+1):
        cur+=math.gcd(math.gcd(a,b),c)
        
  return cur
print(main())

Solution (Python):
from math import gcd
n = int(input())
sum = 0
for i in range(1, n + 1):
    for j in range(1, n + 1):
        for k in range(1, n + 1):
            sum += gcd(gcd(i, j), k)
print(sum)

Solution (Python):
import math
from functools import reduce
from itertools import product
 
x = int(input())
print(sum(map(lambda x: reduce(math.gcd, x), product(range(1, x+1), repeat=3))))

Solution (Python):
import math
from itertools import product
 
x = int(input())

s = 0
for a, b, c in product(range(1, x+1), repeat=3):
  s += math.gcd(math.gcd(a, b), c)
print(s)

Solution (Python):
from math import gcd
K =int(input())

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

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

Solution (Python):
n=3
k=int(input())
INF=10**9+7
l=[0]*k
ans=0
for i in range(k-1,-1,-1):
    x=i+1
    temp=pow(k//x,n,INF)
    for j in range(2,k//x+1):
        temp=(temp-l[j*x-1])%INF
    l[i]=temp
    ans=(ans+x*temp)%INF
print(ans)

Solution (Python):
from math import gcd

K = int(input())

ans = 0

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

print(ans)

Solution (Python):
import bisect,sys
import math
from collections import deque

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))

INF = 1 << 29

DIV = (10**9) + 7

def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max, mod=DIV):
    fac, finv, inv = [0]*max, [0]*max, [0]*max
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, max):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        finv[i] = finv[i-1]*inv[i] % mod

    class CONV:
        def __init__(self):
            self.fac =fac
            self.finv = finv
            pass

        def ncr(self, n, k):
            if(n < k):
                return 0
            if(n < 0 or k < 0):
                return 0
            return fac[n]*(finv[k]*finv[n-k] % DIV) % DIV
        
    return CONV()



sys.setrecursionlimit(200005)


def main():
    N = iRaw()
    ans = 0
    for a in range(1,N+1):
        for b in range(1,N+1):
            for c in range(1,N+1):
                ans+=math.gcd(a,math.gcd(b,c))
    return ans

if __name__ == "__main__":
    print(main())

Solution (Python):
import math
  
def main():
  k=int(input())
  cur=0
  for a in range(1,k+1):
    for b in range(1,k+1):
      for c in range(1,k+1):
        cur+=math.gcd(math.gcd(a,b),c)
        
  return cur
print(main())

Solution (Python):
import sys
from random import choice,randint
inp=sys.stdin.readline
out=sys.stdout.write
flsh=sys.stdout.flush
 
sys.setrecursionlimit(10**9)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]
 
def MI(): return map(int, inp().strip().split())
def LI(): return list(map(int, inp().strip().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines().strip()]
def LI_(): return [int(x)-1 for x in inp().strip().split()]
def LF(): return [float(x) for x in inp().strip().split()]
def LS(): return inp().strip().split()
def I(): return int(inp().strip())
def F(): return float(inp().strip())
def S(): return inp().strip()
def pf(s): return out(s+'\n')
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def main():
    k = I()
    from math import gcd
    s=0
    for i in range(1,k+1):
        for j in range(1,k+1):
            for e in range(1,k+1):
                s+=gcd(gcd(i,j),e)
    print(s)

if __name__ == "__main__":
    main()

Solution (Python):
from math import gcd
z=range(1,1+int(input()))
y=0
for a in z:
  for b in z:
    for c in z:
      y+=gcd(gcd(a,b),c)
print(y)

Solution (Python):
import sys
import numpy as np
import math

from collections import deque 
from functools import reduce
from functools import lru_cache

@lru_cache(maxsize=None)
def gc(a, b):
    if (a % b == 0):
        return b
    return(gc(b, a%b))


n = int(input())

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

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


N = int(input())
add = 0
for i in range(1,N+1):
	for j in range(1,N+1):
		for k in range(1,N+1):
			temp = gcd(i,j)
			add += gcd(temp,k)
print(add)

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

Solution (Python):
import sys
import numpy as np
import math

from collections import deque 
from functools import reduce
from functools import lru_cache



n = int(input())

gcd_num = 0

for i in range(1, n+1):
    for j in range(1, n+1):
        g = math.gcd(i, j)
        for k in range(1, n+1):
            gcd_num += math.gcd(g, k)
print(gcd_num)

Solution (Python):



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



k = int(input())
sum = 0
count = [0] * k

for i in range(1, k + 1):
    for j in range(1, k + 1):
        count[GCD(i, j) - 1] += 1


for i in range(1, k + 1):
    for j, n in enumerate(count):
        sum = sum + GCD(i, j + 1) * n
print(sum)

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

Solution (Python):
GCD = [[-1] * 210 for _ in range(210)]


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


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


if __name__ == "__main__":
    main()

Solution (Python):
from math import gcd
z = range(1, 1+int(input()))
y = 0
for a in z:
  for b in z:
    for c in z:
      y += gcd(gcd(a,b),c)
print(y)

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


k = int(input())

sum = 0


sum += int((1+k)*k/2)


if k >= 2:
    for i in range(1, k):
        for j in range(i+1, k+1):
            sum += gcd(i, j)*6


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

print(sum)

Solution (Python):
from math import gcd
z=range(1,1+int(input()))
y=0
for a in z:
  for b in z:
    for c in z:
      y+=gcd(gcd(a,b),c)
print(y)

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

Solution (Python):
import itertools
import math


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


def main() -> None:
    k = int(input())

    s = sum(gcd(a, b, c) for a, b, c in itertools.product(range(1, k + 1), repeat=3))
    print(s)


if __name__ == "__main__":
    main()

Solution (Python):
import math
n=int(input())
s=0
for i in range(1,n+1):
    for j in range(1,n+1):
        for k in range(1,n+1):
            s+=math.gcd(i,math.gcd(j,k))
print(s)

Solution (Python):
import fractions as ma
import collections
n=int(input())
total=0

d=collections.defaultdict(int)

for a in range(1,n+1):
  for b in range(1,n+1):
    d[ma.gcd(a,b)]+=1
    
for a in range(1,n+1):
  for key in d.keys():
    total += ma.gcd(key,a)*d[key]
      
print(total)

Solution (Python):
from math import gcd
N = int(input())
print(sum([gcd(gcd(i,j),k) for i in range(1,N+1) for j in range(1,N+1) for k in range(1,N+1)]))

Solution (Python):
from math import gcd
N = int(input())
ans = sum([gcd(gcd(i,j),k) for i in range(1,N+1) for j in range(1,N+1) for k in range(1,N+1)])
print(ans)

Solution (Python):
import math

cou = 0
k = int(input())
for a in range(1,k+1):
    for b in range(1,k+1):
        m = math.gcd(a,b)
        for c in range(1,k+1):
            cou += math.gcd(m,c)

print(cou)

Solution (Python):
from math import gcd
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(i, gcd(j, k))
print(ans)

Solution (Python):
from math import gcd

K = int(input())

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

print(res)

Solution (Python):
from math import gcd

K = int(input())

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

print(res)

Solution (Python):
def gcd(a,b):
    if a<b:
        tmp = a
        a = b
        b = tmp
    r = a % b
    while r!=0:
      a = b
      b = r
      r = a % b
    return b
  
def main():
    K = int(input())
    list_ = []
    sum_ = 0
    for i in range(1,K+1):
        for j in range(1,K+1):
            a = gcd(i,j)
            list_.append(a)
    for i in list_:
        for j in range(1,K+1):
            a = gcd(i,j)
            sum_ += a
    print(sum_)

main()

Solution (Python):
K=int(input())

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

s=0
for i in range(1,K+1):
    for j in range(i,K+1):
        m=gcd(i,j)
        for k in range(j,K+1):
            if i==j and j==k:
                s=s+gcd(m,k)
            elif i==j and j!=k:
                s=s+gcd(m,k)*3
            elif i!=j and j==k:
                s=s+gcd(m,k)*3
            else:
                s=s+gcd(m,k)*6
print (s)

Solution (Python):
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)

Solution (Python):

from math import gcd
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)
    
if __name__ == '__main__':
    main()