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

k = int(input())

ans = 0

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

for i in range(1, k+1):
    for j in range(1, k+1):
        IJ[i][j] = math.gcd(i, j)

for i in range(1, k+1):
    for j in range(1, k+1):
        for h in range(1, k+1):
            ans += math.gcd(IJ[i][j], h)


print(ans)

Solution (Python):
import math
from functools import reduce

k = int(input())
ans = 0

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

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

Solution (Python):
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
import math
from functools import reduce


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

memo = []
for i in range(K):
    memo2 = []
    for j in range(K):
        memo2.append([-1] * K)
    memo.append(memo2)


def memorize(i, j, k, a):
    memo[i-1][j-1][k-1] = a

ans = 0
for i in range(1, K+1):
    for j in range(1, K+1):
        for k in range(1, K+1):
            if memo[i-1][j-1][k-1] == -1:
                a = gcd(i, j, k)
                memorize(i,j,k, a)
                memorize(i,k,j, a)
                memorize(j,i,k, a)
                memorize(j,k,i, a)
                memorize(k,i,j, a)
                memorize(k,j,i, a)
                ans += a
            else:
                ans += memo[i-1][j-1][k-1]
print(ans)

Solution (Python):
import sys
import math
input = lambda: sys.stdin.readline().rstrip()
aint = lambda: int(input())

k = aint()
s = 0
for a in range(1,k+1):
    for b in range(a,k+1):
        for c in range(b,k+1):
            gcdab=math.gcd(a,b)
            if a==b and b==c:
                t=1
            elif a==b or b==c:
                t=3
            else:
                t=6
            s += t*math.gcd(gcdab, c)
print(s)

Solution (Python):
import math
k=int(input())
ans=0
er=0
for i in range(1,k+1):
    for j in range(1,k+1):
        for l in range(j,k+1):
            if j==l:
                er = er + math.gcd(i,math.gcd(j,l))
            ans=ans+2*(math.gcd(i,math.gcd(j,l)))

print(ans-er)

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

Solution (Python):
import fractions
K = int(input())
out = 0
L = [0]*K
gcd = [[0]*K for i in range(K)]
for i in range(1,K+1):
    for j in range(1,K+1):
        A = fractions.gcd(i,j)
        gcd[i-1][j-1] = A
        L[A-1]+=1


for i in range(1,K+1):
    for j in range(1,K+1):
        out+=gcd[i-1][j-1]*L[j-1]

print(out)

Solution (Python):
def resolve():
    n=int(input())
    import math
    from functools import reduce
    a=0

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

    for i in range(1,n+1):
        for j in range(1,n+1):
            for k in range(1,n+1):
                a+=gcd([i,j,k])
    print(a)
resolve()

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

import math
from functools import reduce


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

num_range = [int(x) for x in range(1, K+1)]

val = 0

for a in num_range:
    for b in num_range:
        for c in num_range:
            val = val + gcd(a, b, c)

print(val)

Solution (Python):
import math
if __name__ == '__main__':
    
    K = int(input())
    k = 0
    for a in range(1,K+1):
        for b in range(a,K+1):
            for c in range(b,K+1):
                val = math.gcd(math.gcd(a,b),c)
                if a==b or b==c or a==c:
                    if a==b and b==c:
                        val = val
                    else:
                        val = val * 3
                else:
                    val = val * 6

                k = k + val
    print(k)

Solution (Python):
import math
import fractions



def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans
'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  
factinv = [1, 1]  
inv = [0, 1]  

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''









n = int(input())

AB = [[-1 for i in range(n)]for j in range(n)]

for ii in range(n):
    i = ii+1
    for jj in range(n):
        j = jj+1
        AB[ii][jj] = fractions.gcd(i,j)

ans=0
for i in range(n):
    for j in range(n):
        for k in range(n):
            ans += AB[AB[i][j]-1][k]
            
print(ans)

Solution (Python):
from math import gcd

k = int(input())
cache = {}
dp = [-1] * (k + 1)
ans = 0

for x in range(1, k + 1):
    for y in range(1, k + 1):
        xy = gcd(x, y)
        if dp[xy] != -1:
            ans += dp[xy]
        else:
            tmp = 0
            for z in range(1, k + 1):
                tmp += gcd(xy, z)
            ans += tmp
            dp[xy] = tmp
print(ans)

Solution (Python):
from collections import defaultdict
mem = defaultdict(int)
def g(a,b):
    a,b = max(a,b),min(a,b)
    if mem[(a,b)]:return mem[(a,b)]
    c,d = a,b
    while b:a,b=b,a%b
    mem[(c,d)] = a
    return a
d = defaultdict(int)
K = int(input())
ans = 0
lis = []
for a in range(1,K+1):
    for b in range(1,K+1):
        lis.append(g(a,b))
        d[g(a,b)] += 1
lis = list(set(lis))
for c in range(1,K+1):
    for l in lis:
        ans += (d[l]*g(c,l))

print(ans)

Solution (Python):
import math
from functools import reduce

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

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):
from math import gcd
k = int(input())
ans = 0
for i in range(1, k+1):
  for j in range(1, k+1):
    key = gcd(i, j)
    for n in range(1, k+1):
      ans += gcd(key, n)
print(ans)

Solution (Python):
from math import gcd
k=int(input())
d={}
for a in range(1,k+1):
  for b in range(1,k+1):
    g=gcd(a,b)
    if g not in d:
      d[g]=0
    d[g]+=1
print(sum(gcd(a,c)*d[a] for a in d for c in range(1,k+1)))

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

input = sys.stdin.readline

K = int(input())
ans = 0
for a in range(1,K+1):
    for b in range(a,K+1):
        for c in range(b,K+1):
            s = set([a,b,c])
            if len(s) == 1:
                ans += reduce(math.gcd,[a,b,c]) 
            elif len(s) == 2:
                ans += reduce(math.gcd,[a,b,c]) * 3
            else:
                ans += reduce(math.gcd,[a,b,c]) * 6
            
print(ans)

Solution (Python):
import math
from functools import reduce

k = int(input())


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


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)

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

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

Solution (Python):
import math
def g(a,b,c):
    return math.gcd(math.gcd(a,b),math.gcd(b,c))
sum = 0
k = int(input())
for i in range(1,k+1):
    for j in range(1,k+1):
        m = math.gcd(i,j) 
        for l in range(1,k+1):
            sum += math.gcd(m,l)
print(sum)

Solution (Python):
import math

k=int(input())

count=0

for i in range(1,k+1):
    for j in range(1,i):
        tmp_gcd=math.gcd(i,j)
        for l in range(1,k+1):
            count+=2*math.gcd(tmp_gcd,l)
for i in range(1,k+1):
    for l in range(1,k+1):
        count+=math.gcd(i,l)

print(count)

Solution (Python):
import math as m

k = int(input())
ans = 0

for i in range(1, k+1):
    for j in range(i, k+1):
        for n in range(j, k+1):
            g = m.gcd(i, m.gcd(j, n))
            if i == j and j == n:
                ans += g
            elif i == j or j == n or i == n:
                ans += (g * 3)
            else:
                ans += (g * 6)

print(ans)

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

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


import math
from functools import reduce

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


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

from math import gcd


def solve(*args: str) -> str:
    k = int(args[0])

    memo = [[0]*(k+1) for _ in range(k+1)]

    for i in range(1, k+1):
        for j in range(i, k+1):
            m = gcd(i, j)
            memo[i][j] = m
            memo[j][i] = m

    ret = 0
    for a in range(1, k+1):
        for b in range(1, k+1):
            ab = memo[a][b]
            for c in range(1, k+1):
                ret += memo[ab][c]

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Solution (Python):
K = int(input())
def euclid(a, b):
    if b == 0:
        return a
    return euclid(b, a%b)

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

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res

import math 
from collections import defaultdict
from functools import reduce

from itertools import product
k = n_in()


memo = {}

def gcd(a,b):
    if a == 1 or b == 1:
        return 1
    if a == b:
        return a
    if b < a:
        a,b = b,a
    if (a,b) in memo:
        return memo[(a,b)]
    else:
        memo[(a,b)] = math.gcd(a,b)
        return memo[(a,b)]
    
res = 0
for a,b,c in product(range(1,k+1), repeat=3):
    q = gcd(a,b)
    res += gcd(q,c)

print(res)

Solution (Python):



def MI():return map(int,input().split())
def LI():return list(MI())

n=int(input())

import math
from collections import Counter


    

ans=0
t=[]
for i in range(1,n+1):
    for j in range(1,n+1):
        t.append(math.gcd(i,j))
        
c=Counter(t).items()

for (i,j) in c:
    for k in range(1,n+1):
        ans+=math.gcd(i,k)*j
        
print(ans)

Solution (Python):
from math import gcd
import functools

K = int(input())
ans = 0
for a in range(1, K+1):
    for b in range(a, K+1):
        for c in range(b, K+1):
            i = (a, b, c)
            length = len(set(i))
            if length == 1:
                ans = ans + a
            elif length == 2:
                ans = ans + 3 * (functools.reduce(gcd, [a, b, c]))
            elif length == 3:
                ans = ans + 6 * (functools.reduce(gcd, [a, b, c]))
                         
print(ans)

Solution (Python):
a = [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]
n = int(input())
print(a[n-1])

Solution (Python):
gcd_mp = {}

def gcd(a, b):
    global gcd_mp
    key = tuple(sorted([a, b]))
    if key not in gcd_mp:
        while b:
            a, b = b, a % b
        gcd_mp[key] = a
    return gcd_mp[key]

K = int(input())

ab_gcd = {}

for a in range(1, K + 1):
    for b in range(1, K + 1):
        val = gcd(a, b)
        if val not in ab_gcd:
            ab_gcd[val] = 0
        ab_gcd[val] += 1

total = 0

for key, val in ab_gcd.items():
    for c in range(1, K + 1):
        total += gcd(key, c) * val

print(total)

Solution (Python):
import math
 
K = int(input())
 
ans = 0
for i in range(1, K+1):
  for j in range(i+1, K+1):
    for k in range(j+1, K+1):
        ans += math.gcd(i, math.gcd(j, k)) * 6

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

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

Solution (Python):
from collections import defaultdict
def gcd(x,y):
    while y:
        x, y = y, x%y 
    return x

K=int(input())
gcd_of_two = defaultdict(int)
for i in range(1, K+1):
    for j in range(1, K+1):
        gcd_of_two[gcd(i,j)] += 1
result = 0
for val, freq in gcd_of_two.items():
    for k in range(1,K+1):
        result += freq * gcd(val, k)
print(result)

Solution (Python):
import math
import collections
import sys

input = sys.stdin.readline
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]

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

k=I()
s1=k*(k+1)//2
s2=0
for i in range(1,k):
    for j in range(i+1,k+1):
        s2+=gcd(i,j)
s2=6*s2

s3=0
for i in range(1,k-1):
    for j in range(i+1,k):
        for l in range(j+1,k+1):
            s3+=6*gcd(gcd(i,j),l)

ans=s1+s2+s3
print(ans)

Solution (Python):
import math
def gcd(a, b, c):
    x = math.gcd(a, b)
    return(math.gcd(x, c))
K = int(input())
sum = 0
for i in range(1, K + 1):
    for j in range(i, K + 1):
        for k in range(j, K + 1):
            if i == j == k:
                sum += gcd(i, j, k)
            elif i == j or j == k or k == i:
                sum += 3 * gcd(i, j, k)
            else:
                sum += 6 * gcd(i, j, k)
print(sum)

Solution (Python):
import math
ans = 0
K = int(input())
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)

Solution (Python):

import sys
from math import gcd

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

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

print(answer)

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

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

table=[[[None]*n for _ in range(n)] for _ in range(n)]
ans=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:
                if j==k:
                    ans+=gcd(gcd(i,j),k)
                else:
                    ans+=gcd(gcd(i,j),k)*3
            elif j==k:
                ans+=gcd(gcd(i,j),k)*3
            else:
                ans+=gcd(gcd(i,j),k)*6
            
print(ans)

Solution (Python):
import math

K = int(input())

sum_list = []
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            tmp = math.gcd(a,b)
            tmp = math.gcd(c,tmp)
            sum_list.append(tmp)


ans = sum(sum_list)
print(ans)

Solution (Python):
import math

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

print(ans)

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):
        tmp = gcd(i, j)
        if tmp == 1:
            ans += K
        else:
            for k in range(1, K + 1):
                ans += gcd(tmp, k)

print(ans)

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

k = int(input())

ans = 0

for abc in itertools.product(range(1, k + 1), repeat=3):
    ans += reduce(math.gcd, abc)

print(ans)

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

Solution (Python):
N=int(input())
import math
ans=(N+1)*N//2
for i in range(N-1):
  for j in range(i+1,N):
    ans+=math.gcd(i+1,j+1)*6
    
for i in range(N-2):
  for j in range(i+1,N-1):
    for k in range(j+1,N):
      ans+=math.gcd(math.gcd(i+1,j+1),k+1)*6
print(ans)

Solution (Python):
from fractions import gcd
ans=0
K=input()
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

Solution (Python):
from collections import defaultdict
def gcd(a,b):
    if a==0:
        return b
    return gcd(b%a,a)
N=int(int(input()))
ans=0
Hash=defaultdict(lambda:0)
for i in range(1,N+1):
    for j in range(1,N+1):
        x=gcd(i,j)
        Hash[x]+=1
for i in range(1,N+1):
    for j,t in Hash.items():
        x=gcd(j,i)
        ans+=t*x
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):
        kari=gcd(i,j)
        for k in range(1,K+1):
            ans+=gcd(kari,k)
print(ans)

Solution (Python):
import math
count = 0
x = int(input())
for i in range(x):
  for j in range(x):
    v = math.gcd(i+1,j+1)
    for k in range(x):
      count += math.gcd(v,k+1)

print(count)

Solution (Python):
import math
n = int(input())
m = 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):
            b = math.gcd(a, k)
            m += b
print(m)

Solution (Python):
def main():
    k=int(input())
    n=3
    A=[0]*(k+1)
    A[k]=1
    for i in range(1,k)[::-1]:
        l=k//i
        A[i]=pow(l,n)
        for j in range(2,l+1):
            
            A[i]-=A[i*j]
    
    ans=0
    for i in range(1,k+1):
        ans+=A[i]*i
    print(ans)
    
if __name__=='__main__':
    main()

Solution (Python):
import math
from functools import reduce

K = int(input())

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

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

Solution (Python):
import math

k = int(input())
ans = 0

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

Solution (Python):
import math


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

    GCD = [[0] * 201 for i in range(201)]
    for ki1 in range(1, k + 1):
        for ki2 in range(1, k + 1):
            GCD[ki1][ki2] = math.gcd(ki1, ki2)

    ans = 0
    for ki1 in range(1, k + 1):
        for ki2 in range(1, k + 1):
            for ki3 in range(1, k + 1):
                ans += GCD[GCD[ki1][ki2]][ki3]

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import fractions


if __name__ == "__main__":
    K = int(input())

    d = {}

    result = 0
    for i in range(1, K+1):
        for j in range(1, K+1):
            gcd_ab = fractions.gcd(i, j)
            if gcd_ab not in d:
                d[gcd_ab] = 0
            d[gcd_ab] += 1

    for gcd_ab, count in d.items():
        for k in range(1, K+1):
            result = result + fractions.gcd(gcd_ab, k) * count

    print(result)

Solution (Python):
import sys
import math

input = sys.stdin.readline

K = int(input())
ans = 0
for i in range(1, K + 1):
    for j in range(i, K + 1):
        n = math.gcd(i, j)
        for l in range(j, K + 1):
            if len(set([i, j, l])) == 1:
                ans += math.gcd(n, l)
            elif len(set([i, j, l])) == 2:
                ans += (math.gcd(n, l) * 3)
            else:
                ans += (math.gcd(n, l) * 6)

print(ans)

Solution (Python):
import math
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

print(ans)

Solution (Python):

import math
K = int(input())
rep = 0
gcds = [[0 for i in range(201)] for _ in range(201)]
for a in range(1,K+1):
    for b in range(1,K+1):
        gcds[a][b] = math.gcd(a,b)
for a in range(1,K+1):
    for b in range(1, K+1):
        for c in range(1, K+1):
            rep += gcds[gcds[a][b]][c]
print(rep)

Solution (Python):
def gcd2(x, y):
    if y == 0:
        return x
    else:
        return gcd2(y, x % y)
def gcd3(x,y,z):
    return gcd2(gcd2(x, y), z)

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

print(ans)

Solution (Python):
def gcd(x,y):
    if memo[x][y] != 0:
        return memo[x][y]
    tmp_x = x
    tmp_y = y
    while y != 0:
        x,y = y,x%y
    memo[tmp_x][tmp_y] = x
    memo[tmp_y][tmp_x] = x
    return x

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

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

for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            ans += memo[memo[i][j]][k]

print(ans)

Solution (Python):
from math import gcd

K = int(input())

print(sum(gcd(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)))

Solution (Python):
import math

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

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

print(ans)

Solution (Python):




import math
from functools import reduce

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

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

def gcd_list(numbers):
    return reduce(math.gcd, numbers)
    
if __name__ == '__main__':
    main()

Solution (Python):
k=int(input())
ans=0
from math import gcd
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
x = 0
n = int(input())
for i in range(n):
    for j in range(n):
        t = math.gcd(i+1,j+1)
        if t == 1:
            x += n
            continue
        for k in range(n):
            x += math.gcd(t, k+1)
print(x)

Solution (Python):
def main():
    K = int(input())
    s = 0
    import math
    for i in range(1,K+1):
        for j in range(1,K+1):
            ij = math.gcd(i,j)
            if ij == 1:
                s += 1 * K
            else:
                for k in range(1,K+1):
                    s += math.gcd(ij,k)
    print(s)



if __name__ == "__main__":
    main()

Solution (Python):
def main():
    import sys
    from fractions import gcd
    sys.setrecursionlimit(10 ** 6)
    input = sys.stdin.readline
    K = int(input())
    GCD = {}
    for a in range(1, K+1):
        for b in range(1, K+1):
            GCD[(a, b)] = gcd(a, b)
    ans = 0
    for a in range(1, K+1):
        for b in range(1, K+1):
            gcd_ = GCD[(a, b)]
            for c in range(1, K+1):
                ans += GCD[(gcd_, c)]
                
    print(ans)
    

if __name__ == '__main__':
    main()

Solution (Python):
from math import gcd
from itertools import combinations
N=int(input())
dif3=list(combinations(range(1,N+1), 3))
dif2=list(combinations(range(1,N+1),2))
res = 0
for i in dif3:
    a = gcd(i[0], i[1])
    res += 6 * gcd(a, i[2])
for i in dif2:
    res += 6 * gcd(i[0], i[1])
res += int(N*(N+1)/2)
print(res)

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

def gcd_3(a,b,c):
    x = math.gcd(a,b)
    y = math.gcd(x,c)
    return y
li = []
count = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        li.append(math.gcd(i,j))
for i in range(1,len(li)+1):
    for j in range(1,k+1):
        count += math.gcd(li[i-1],j)
print(count)

Solution (Python):
import heapq
import math
from collections import defaultdict
from itertools import permutations,combinations,combinations_with_replacement
from functools import reduce

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

K = int(input())
res = 0

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

print(res)

Solution (Python):

import math
from functools import reduce

k = int(input())
s = 0
for i in range(1, k+1):
    for j in range(1, k+1):
        for k in range(1, k+1):
            s += reduce(math.gcd, [i, j, k])

print(s)

Solution (Python):
import math
K =int(input())
sum_num = 0
for i in range(K):
    for j in range(i+1):
        temp_gcd = math.gcd(i+1,j+1)
        if i != j:
            same = False
        else:
            same = True
        for k in range(j+1):
            temp_num = math.gcd(temp_gcd,k+1)
            if same:
                if i != k and j != k:
                    sum_num += temp_num * 3
                else:
                    sum_num += temp_num 
            else:
                if i != k and j != k:
                    sum_num += temp_num * 6
                else:
                    sum_num += temp_num * 3

                
                
print(sum_num)

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



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

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):
            l = [i, j, k]
            result += gcdlist(l)

print(result)

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

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

print(ans)

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

import math
from functools import reduce
import itertools


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

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

ans = 0

for a, b, c in itertools.combinations_with_replacement(range(1, K + 1), 3):
    if a == b == c:
        x = 1
    elif a == b or b == c or c == a:
        x = 3
    else:
        x = 6
    ans += gcd(a, b, c) * x

print(ans)

Solution (Python):
from  math import gcd
dic = {}
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 and b == c:
                sum_ += gcd(gcd(a, b),c)
            elif a == b or b == c or c == a:
                sum_ += gcd(gcd(a, b),c)*3
            else:
                sum_ += gcd(gcd(a, b),c)*6
print(sum_)

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

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

Solution (Python):
import math
from functools import reduce
def gcd_list(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_list([a,b,c])

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

print(ans)