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 bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(100000)
# mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 

P = {}
def gcd(a, b):
    if a > b:
        a, b = b, a
    if (a, b) in P:
        return P[(a, b)]
    
    v = math.gcd(a, b)
    P[(a, b)] = v
    return v


def main():
    K = int(input()) - 1
    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]
    print(A[K])


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

k = int(input())

s = 0
x = []
for a in range(1,k+1):
    for b in range(1,k+1):
        x.append(math.gcd(a,b))
for y in x:
    for c in range(1,k+1):
        s+=math.gcd(y,c)
print(s)

Submission status: Accepted

Solution code:
import math
from functools import lru_cache

ls_gcd  = [[None for _ in range(201)] for _ in range(201)]
for i in range(201):
    for j in range(201):
        ls_gcd[i][j] = math.gcd(i,j)

# def gcd(a,b,c):
#     # ab = math.gcd(a,b)
#     # abc = math.gcd(ab,c)
#     ab = ls_gcd[a][b]
#     abc = ls_gcd[ab][c]
#     return abc

K = int(input())
ans = 0
for i in range(K):
    for j in range(K):
        ab = ls_gcd[i+1][j+1]
        t = ls_gcd[ab]
        for k in range(K):
            ans += t[k+1]
print (ans)

Submission status: Accepted

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

total = 0
for i in range(k):
    for j in range(k):
        ij_gcd = math.gcd(i+1, j+1)
        if ij_gcd == 1:
            total+=k
            continue
        for l in range(k):
            total+=math.gcd(l+1, ij_gcd)

print(total)

Submission status: Accepted

Solution code:
import math

N = input()
N = int(N)

gcds = []

for i in range(0,N):
  gcds.append([])
  for j in range(0,N):
    gcds[i].append(math.gcd(i+1,j+1))


sum = 0
for i in range(0,N):
    for j in range(0,N):
        for k in range(0,N):
            sum += gcds[ gcds[i][j] -1 ][k]

print(sum)

Submission status: Accepted

Solution code:
import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)
counter = 0
n = int(input())
list = [0] * (n + 1)
for l in range(1, n + 1):
    for m in range(1, n + 1):
        list[gcd(l, m)] += 1
for l in range(1, n + 1):
    for m in range(1, n + 1):
        counter += gcd(l, m) * list[l]

print(counter)

Submission status: Accepted

Solution code:
import math

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
if __name__ == '__main__':
    #s = input().rstrip().split(' ')
    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)

Submission status: Accepted

Solution code:
import math
import fractions
#import sys
#input = sys.stdin.readline

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)

    # divisors.sort()
    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]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

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)

'''

#a = list(map(int, input().split()))

#################################################
#################################################
#################################################
#################################################


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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8
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())))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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 # version 3.4
from collections import defaultdict
from functools import reduce

from itertools import product
k = n_in()
#k = 200

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)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

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

n=int(input())

import math
from collections import Counter

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

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
        # p\rint(c)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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
#print(s1,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)
#print(s3)
ans=s1+s2+s3
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
# coding: utf-8
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)

Submission status: Accepted

Solution code:
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)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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):
            #print(i,i*j)
            A[i]-=A[i*j]
    #print(A)
    ans=0
    for i in range(1,k+1):
        ans+=A[i]*i
    print(ans)
    
if __name__=='__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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