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 math

k = int(input())
ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
# ABC162 C

import math

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

    res = []

    for i in range(1, k+1):
        for j in range(1, k+1):
            for l in range(1, k+1):
                gcd = math.gcd(i, j)
                if gcd==1:
                    res.append(1)
                else:
                    res.append(math.gcd(gcd ,l))
    
    print(sum(res))

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import math
N=int(input())
g1=[math.gcd(x,y) for x in range(1,N+1) for y in range(1,N+1)]
g2=[math.gcd(x,y) for x in g1 for y in range(1,N+1)]
print(sum(g2))

Submission status: Accepted

Solution code:
import math

l = []
k = int(input())
for i in range(k):
  for j in range(k):
    x = math.gcd(i+1, j+1)
    for h in range(k):
      l.append(math.gcd(x, h+1))
      
print(sum(l))

Submission status: Accepted

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

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

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

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

print(ans)

Submission status: Accepted

Solution code:
import itertools
import math
from functools import reduce

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

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,j,k)
            

print(ans)

Submission status: Accepted

Solution code:
import math

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

for l in range(1, k+1):
    for h in chk_list:
        ans += math.gcd(l, h)

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

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

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

print(ans)

Submission status: Accepted

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

main()

Submission status: Accepted

Solution code:
import math

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

tot += sum(range(1, K + 1))
print(tot)

Submission status: Accepted

Solution code:
import math
from functools import lru_cache

@lru_cache(maxsize=None)
def gcd(x, y):
    return math.gcd(x, y)


k = int(input())
answer = 0
ary = []
for a in range(1, k + 1):
    for b in range(1, k + 1):
        if a >= b:
            ary.append(gcd(b, a))
        else:
            ary.append(gcd(a, b))

h = {}
for a in ary:
    if a not in h:
        h[a] = 0
    h[a] += 1
# print(h)

for x in h.keys():
    for c in range(1, k + 1):
        answer += gcd(x, c) * h[x]
print(answer)

Submission status: Accepted

Solution code:
import math
from functools import reduce
N = int(input())
total = 0
def gcd(*numbers):
    return reduce(math.gcd, numbers)
def gcd_list(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):
            total += gcd(i, j, k)
print(total)

Submission status: Accepted

Solution code:
from math import gcd
from itertools import product
k = int(input())
partial_gcd = (gcd(a, b) for a, b in product(range(1, k+1), range(1, k+1)))
print(sum(gcd(part, c) for part, c in product(partial_gcd, range(1, k+1))))

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(i, K+1):
        for k in range(j, K+1):
            tmp = gcd(gcd(i, j), k) * 6
            if i == j and j == k: tmp //= 6
            elif i == j or j == k or k == i: tmp //= 2
            ans += tmp
print(ans)

Submission status: Accepted

Solution code:
import math
k = int(input())
ans = 0
if k < 3:
    for i in range(1,k+1):
        for j in range(1,k+1):
            for n in range(1,k+1):
                ans += math.gcd(i,math.gcd(j,n))
else: 
    #i*j
    for n in range(1,k+1):
        for i in range(1,k+1):
            ans += math.gcd(n,i)
            for j in range(i+1,k+1):            
                ans += 2*(math.gcd(math.gcd(i,j),n))

    '''
        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))
    '''
print(ans)

Submission status: Accepted

Solution code:
import sys
import math

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

IN=lambda : map(int, input().split())
mod=1000000007

#+++++

def main():
	k = int(input())
	#b , c = IN()
	#s = 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 += math.gcd(math.gcd(i,j),k)
	return s
	
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
from math import gcd

k = int(input())

po = [ gcd(a, gcd(b, c)) for a in range(1, k+1) for b in range(1, k+1) for c in range(1, k+1)]

print(sum(po))

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 = ans + gcd(a,b,c)
print(str(ans))

Submission status: Accepted

Solution code:
import math
from functools import reduce

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

Submission status: Accepted

Solution code:
import math
from functools import reduce

k = int(input())

result = 0

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

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:
                result += a
            elif a == b and a!= c:
                result += gcd(a, c)*3
            elif a == c and a != b:
                result += gcd(a, b)*3
            elif b == c and a != b:
                result += gcd(a, b)*3
            else:
                result += gcd(a, b, c)*6
print(result)

Submission status: Accepted

Solution code:
gcd_memo = {}


def gcd(a, b):
    if b == 0:
        return a
    elif (a, b) in gcd_memo:
        return gcd_memo[(a, b)]
    else:
        r = a % b
        gcd_memo[(a, b)] = gcd(b, r)
        gcd_memo[(b, a)] = gcd_memo[(a, b)]
        return gcd_memo[(a, b)]


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

Submission status: Accepted

Solution code:
K = int(input())
ans1 = 0
ans2 = 0
ans3 = 0

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

def gn(num):
    value = num[0]
    for item in num[1:]:
        value = gcd(value, item)
    return value


a = gn([3,15,18])

import itertools

seq = [x+1 for x in range(K)]
ptr = list(itertools.combinations(seq,3))

for i in range(len(ptr)):
    ans1 += gn(ptr[i])*6
    
seq2 = [x+1 for x in range(K)]
ptr2 = list(itertools.combinations(seq2,2))

for i in range(len(ptr2)):
    ans2 += gcd(ptr2[i][0],ptr2[i][1])*6
    
ans3 = K*(K+1)/2
print(int(ans1+ans2+ans3))

Submission status: Accepted

Solution code:
from math import gcd

def match(a, b, c):
    if a == b == c:
        return a
    if a == b or b == c:
        return gcd(gcd(a, b), c) * 3
    return gcd(gcd(a, b), c) * 6

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

    for a in range(1, K+1):
        for b in range(a, K+1):
            for c in range(b, K+1):
                answer += match(a, b, c)
    print(answer)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)
K=int(input())
sum = 0
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            sum = sum + gcd(a,b,c)
print(sum)

Submission status: Accepted

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


import math
from functools import reduce

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


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


print(sum)

Submission status: Accepted

Solution code:
import math
from functools import reduce
K=int(input())
a=0
def gcd(*numbers):
    return reduce(math.gcd,numbers)
#def gcd_list(numbers):
 #   return reduce(math.gcd,numbers)
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            a+=gcd(i,j,k)
print(a)

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

Submission status: Accepted

Solution code:
import math

K = int(input())

GCD=[[0]*201]*201

A=0
#for i in range(1,K+1):
#    for j in range(1,K+1):
#        GCD[i][j]=math.gcd(i,j)
#        print(i,j,GCD[i][j])

for i in range(1,K+1):
    for j in range(1,K+1):
        t=math.gcd(i,j)
        for k in range(1,K+1):
#            t = GCD[i][j]
#            A += GCD[t][k]
#            print(i,j,k,t,GCD[t][k])
            A+=math.gcd(t,k)

print(A)

Submission status: Accepted

Solution code:
import math
from itertools import combinations
from functools import reduce


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


K = int(input())
ans = 0
for abc in combinations(range(1, K+1), 3):
    ans += gcd_3(*abc) * 6

for a, b in combinations(range(1, K+1), 2):
    ans += math.gcd(a, b) * 6

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

print(ans)

Submission status: Accepted

Solution code:
from fractions import *
k = int(input())
ans = 0

gcd_list = [[0] * k for i in range(k)]
for i in range(k):
    gcd_list[0][i] = 1
for b in range(1, k + 1):
    for c in range(1, k + 1):
        if not gcd_list[b - 1][c - 1]:
            gcd_list[b - 1][c - 1] = gcd(b, c)
            
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 - 1][gcd_list[b - 1][c - 1] - 1]
print(ans)

Submission status: Accepted

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

k = int(input())
200
s = 0

for i in range(k):
    s += (i + 1)

if k == 1:
    print(s)
else:
    for i in range(1,k):
        for j in range(i + 1,k + 1):
            s += 6 * (gcd(j,i))
    if k == 2:
        print(s)
    else:
        for i in range(1,k-1):
            for j in range(i + 1,k):
                for k in range(j + 1,k + 1):
                    x = gcd(j,i)
                    y = gcd(k,x)
                    s += 6 * y
        print(s)

Submission status: Accepted

Solution code:
K = int(input())

import fractions

A = {}
sum = 0

for i in range(K):
    for j in range(K):
        if fractions.gcd(i+1,j+1) in A:
            A[fractions.gcd(i+1,j+1)] += 1
        else:
            A[fractions.gcd(i+1,j+1)] = 1

for key in A:
    for i in range(K):
        sum += fractions.gcd(key,i+1)*A[key]

print(sum)

Submission status: Accepted

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

bc = []
for b in range(1, K + 1):
    for c in range(1, K + 1):
       bc.append(math.gcd(b, c))
ans = 0
for a in range(1,  K + 1):
    for g in bc:
        ans += math.gcd(g, a)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
ans = 0
for i in range(1, n+1):
  for j in range(i, n+1):
    for k in range(j, n+1):
      b = 1
      for m in range(1, i + 1):
        if i%m == 0 and j%m == 0 and k%m == 0:
          b = m
      if i == j == k:
        ans += b
      elif i != j and j != k:
        ans += 6*b
      else:
        ans += 3*b
print(ans)

Submission status: Accepted

Solution code:
import math

a=int(input())

t=0
"""
for i in range(1,a+1):
  for j in range(i,a+1):
    for k in range(j,a+1):
      
      print(i,j,k)

      if i==j and j==k:
        t+=math.gcd(math.gcd(i,j),k)
      else:
        t+=(math.gcd(math.gcd(i,j),k)*3)

print(t)
"""

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

Submission status: Accepted

Solution code:
import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)
def gcd_list(numbers):
    return reduce(math.gcd, numbers)


n=int(input())
ans=0

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

print(ans)

Submission status: Accepted

Solution code:
from functools import reduce
from itertools import combinations

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

def gcd_list(A): return reduce(gcd, A)

K = int(input())
S = K * (K + 1) // 2
for a, b in combinations(range(1, K+1), 2):
    S += 6 * gcd(a, b)
for a, b, c in combinations(range(1, K+1), 3):
    S += 6 * gcd_list((a, b, c))
print(S)

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

Submission status: Accepted

Solution code:
import math
from functools import reduce


K = int(input())
res = [[[0] * (K+1) for i in range(K+1)] for j in range(K+1)]


def gcd(numbers):
    global res

    numbers.sort()
    if res[numbers[0]][numbers[1]][numbers[2]] > 0:
        return res[numbers[0]][numbers[1]][numbers[2]]
    else:
        val = reduce(math.gcd, (numbers[0], numbers[1],numbers[2]))
        res[numbers[0]][numbers[1]][numbers[2]] = val
        return val


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:
#k
k=int(input())

ans = [0
,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(ans[k])

Submission status: Accepted

Solution code:
# ANSHUL GAUTAM
# IIIT-D

from math import *
from copy import *
from heapq import *
from string import *				# alpha = ascii_lowercase
from random import *				# l.sort(key=lambda l1:l1[0]-l1[1]) => ex: sort on the basis difference
from bisect import *				# bisect_left(arr,x,start,end)  => start and end parameters are temporary
from sys import stdin				# bisect_left return leftmost position where x should be inserted to keep sorted
from sys import maxsize
from operator import *				# d = sorted(d.items(), key=itemgetter(1))
from itertools import *
from collections import Counter		# d = dict(Counter(l))
from collections import defaultdict # d = defaultdict(list)

'''

'''

def Sieve(x):
	checkPrime = [1 for i in range(x+1)]
	zz = 2
	L = []
	while(zz**2 <= x):
		if(checkPrime[zz] == 1):
			for i in range(zz*2,x+1,zz):
				checkPrime[i] = 0
		zz += 1
	for i in range(2,x):
		if(checkPrime[i] == 1):
			L.append(i)
	return checkPrime

primes = Sieve(200)

def solve(x):
	ans = 0
	z = 0
	# x = 200
	d = defaultdict(int)
	# dp = [0]*3
	ans = 0
	# x = 3
	for i in range(1,x+1):
		for j in range(1,x+1):
			for k in range(1,x+1):
				# z += 1
				g = gcd(gcd(i,j),k)
				# d[g] += 1
				# print(i,j,k,'-->',g)
				ans += g
				# if(i == j == k):
				# 	dp[i-1] = ans
				# 	print('------'*4)
	# print(d)
	# print(dp)
	# ans = 
	# ans += 1
	# ans = 0
	# for i in range(1,x+1):
	# 	for j in range(i+1,x+1):
	# 		for k in range(j+1,x+1):
	# 			ans += 1
	return ans

N = int(stdin.readline())
ans = solve(N)
print(ans)

Submission status: Accepted

Solution code:
from functools import lru_cache

k = 0

def format_input(filename = None):
	global k
	if filename == None:
		k = int(input())

	elif filename == '__random__':
		from random import randint as rng
		k = rng(1, 2 * 10**2)
		print(k)

@lru_cache(maxsize=None)
def gcd(a, b):
	i, j = a, b
	while j > 0:
		i %= j
		i, j = j, i
	return i

def get_answer():
	answer = 0
	for a in range(1, k+1):
		for b in range(1, k+1):
			for c in range(1, k+1):
				answer += gcd(a, gcd(b, c))
	return answer

if __name__ == '__main__':
	format_input()

	ans = get_answer()
	print(ans)

Submission status: Accepted

Solution code:
import math

K = int(input())
arr = []
a = 0
for i in range(1,K+1):
  for j in range(1,K+1):
    arr.append(math.gcd(i, j))      
for j in range(len(arr)):
  for k in range(1,K+1):
    a += math.gcd(arr[j],k)
print(int(a))

Submission status: Accepted

Solution code:
N = int(input())

import itertools
h = itertools.combinations_with_replacement(list(range(1,N+1)), 3)

import math
from functools import reduce

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

ans = 0
for n1, n2, n3 in h:
  #print("{} {} {}".format(n1,n2,n3))
  if n1 == n2 == n3:
    ans += gcd(n1,n2,n3)
  elif n1 == n2 or n1 == n3 or n2 == n3:
    ans += gcd(n1,n2,n3)*3
  else:
    ans += gcd(n1,n2,n3)*6
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
import math
K = int(stdin.readline().rstrip())
ans = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            tmp = math.gcd(i,j)
            ans += math.gcd(tmp,k)
print(ans)

Submission status: Accepted

Solution code:
import math
from functools import reduce
N = int(input())
 
 
def gcd(*numbers):
    return reduce(math.gcd, numbers)
 
 
sum_N = 0
for i in range(1, N + 1):
    for j in range(1, N + 1):
        for k in range(1, N + 1):
            sum_N += gcd(i, j, k)
 
print(sum_N)

Submission status: Accepted

Solution code:
import math
from functools import reduce
def gcd(*numbers):
    return reduce(math.gcd, numbers)
n=int(input())
ans = 0
for i in range(n):
    for j in range(i,n):
        for k in range(j,n):
            if i==j==k:
              ans+=gcd(i+1,j+1,k+1)
            elif i<j<k:
              ans+=6*(gcd(i+1,j+1,k+1))  
            else:
              ans+=3*(gcd(i+1,j+1,k+1))
print(ans)

Submission status: Accepted

Solution code:
import math
import itertools
k = int(input())
t = list(map(lambda x:list(x),itertools.product([i+1 for i in range(k)],repeat=2)))
ans = 0
for i in range(len(t)):
    cu = math.gcd(t[i][0],t[i][1])
    for j in range(1,k+1):
        ans += math.gcd(j,cu)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

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[N-1])

Submission status: Accepted

Solution code:
import math
k = int(input())
result = 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) == 3:
        result += 6 * math.gcd(math.gcd(a,b),c)
      if len(s) == 2:
        result += 3 * math.gcd(math.gcd(a,b),c)
      if len(s) == 1:
        result += math.gcd(math.gcd(a,b),c)
      
       
        
      
      
      
      
print(result)

Submission status: Accepted

Solution code:
# coding: utf-8


def euclid(n, m):

    def rec(n, m):
        if n % m == 0:
            return m
        
        return rec(m, n % m)
    
    return rec(n, m)


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

    ans = 0
    memo = {}
    for a in range(1, K+1):
        for b in range(a, K+1):
            for c in range(b, K+1):
                key_ab = f"{a}_{b}"
                if key_ab in memo:
                    euc_ab = memo[key_ab]
                else:
                    euc_ab = euclid(a, b)
                    memo[key_ab] = euc_ab
                
                x, y = sorted([euc_ab, c])

                key_xy = f"{x}_{y}"
                if key_xy in memo:
                    euc_xy = memo[key_xy]
                else:
                    euc_xy = euclid(x, y)
                    memo[key_xy] = euc_xy

                if a == b == c:
                    ans += euc_xy
                elif (a == b and b != c) or (b == c and c != a) or (c == a and a != b):
                    ans += euc_xy * 3
                else:
                    ans += euc_xy * 6

    return ans


print(main())

Submission status: Accepted

Solution code:
import math

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

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
from heapq import heapify, heappop, heappush
from sys import stdin

d = dict()


def gcd(a, b):
    if (a, b) in d:
        return d[(a, b)]
    if b == 0:
        return a
    else:
        res = gcd(b, a % b)
        d[(a, b)] = res
        return res
    return


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


def main():
    res = 0
    n = int(input())
    for a in range(1, n+1):
        for b in range(1, n+1):
            m = gcd(a, b)
            if m == 1:
                res += 1*n
            else:
                for c in range(1, n+1):
                    res += gcd(m, c)
    print(res)


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


main()

Submission status: Accepted

Solution code:
import math
from functools import reduce

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

n = int(input())
sum = 0

for i in range(1,n+1):
    for j in range(1,i+1):
        for k in range(1,j+1):
            if i == j and 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

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

print(sum)

Submission status: Accepted

Solution code:
import math
from functools import reduce

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

k = int(input())

ans = 0
l = []
for a in range(1, k+1):
    for b in range(1, k+1):
        l.append(math.gcd(a, b))

for li in l :
    for c in range(1, k+1):
        ans += math.gcd(li, c)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
k = int(input())
dp = [[1 for _ in range(k + 1)] for _ in range(k + 1)]
for i in range(1, k + 1):
    for j in range(1, k + 1):
        dp[i][j] = math.gcd(i, j)
ans = 0
for a in range(1, k + 1):
    for b in range(1, k + 1):
        for c in range(1, k + 1):
            ans += dp[a][dp[b][c]]
print(ans)

Submission status: Accepted

Solution code:
a = {"1": 1, "2": 9, "3": 30, "4": 76, "5": 141, "6": 267, "7": 400, "8": 624, "9": 885, "10": 1249, "11": 1590, "12": 2208, "13": 2689, "14": 3411, "15": 4248, "16": 5248, "17": 6081, "18": 7485, "19": 8530, "20": 10248, "21": 11889, "22": 13687, "23": 15228, "24": 17988, "25": 20053, "26": 22569, "27": 25242, "28": 28588, "29": 31053, "30": 35463, "31": 38284, "32": 42540, "33": 46581, "34": 50893, "35": 55362, "36": 61824, "37": 65857, "38": 71247, "39": 76884, "40": 84388, "41": 89349, "42": 97881, "43": 103342, "44": 111528, "45": 120141, "46": 128047, "47": 134580, "48": 146316, "49": 154177, "50": 164817, "51": 174438, "52": 185836, "53": 194157, "54": 207927, "55": 218812, "56": 233268, "57": 245277, "58": 257857, "59": 268182, "60": 288216, "61": 299257, "62": 313635, "63": 330204, "64": 347836, "65": 362973, "66": 383709, "67": 397042, "68": 416448, "69": 434025, "70": 456967, "71": 471948, "72": 499740, "73": 515581, "74": 536073, "75": 559758, "76": 583960, "77": 604833, "78": 633651, "79": 652216, "80": 683712, "81": 709065, "82": 734233, "83": 754734, "84": 793188, "85": 818917, "86": 846603, "87": 874512, "88": 909496, "89": 933081, "90": 977145, "91": 1006126, "92": 1041504, "93": 1073385, "94": 1106467, "95": 1138536, "96": 1187112, "97": 1215145, "98": 1255101, "99": 1295142, "100": 1342852, "101": 1373253, "102": 1422195, "103": 1453816, "104": 1502376, "105": 1553361, "106": 1595437, "107": 1629570, "108": 1691292, "109": 1726717, "110": 1782111, "111": 1827492, "112": 1887772, "113": 1925853, "114": 1986837, "115": 2033674, "116": 2089776, "117": 2145333, "118": 2197483, "119": 2246640, "120": 2332104, "121": 2379085, "122": 2434833, "123": 2490534, "124": 2554600, "125": 2609625, "126": 2693919, "127": 2742052, "128": 2813988, "129": 2875245, "130": 2952085, "131": 3003306, "132": 3096024, "133": 3157249, "134": 3224511, "135": 3306240, "136": 3388576, "137": 3444609, "138": 3533637, "139": 3591322, "140": 3693924, "141": 3767085, "142": 3842623, "143": 3912324, "144": 4027884, "145": 4102093, "146": 4181949, "147": 4270422, "148": 4361548, "149": 4427853, "150": 4548003, "151": 4616104, "152": 4718640, "153": 4812789, "154": 4918561, "155": 5003286, "156": 5131848, "157": 5205481, "158": 5299011, "159": 5392008, "160": 5521384, "161": 5610705, "162": 5739009, "163": 5818390, "164": 5930196, "165": 6052893, "166": 6156139, "167": 6239472, "168": 6402720, "169": 6493681, "170": 6623853, "171": 6741078, "172": 6864016, "173": 6953457, "174": 7094451, "175": 7215016, "176": 7359936, "177": 7475145, "178": 7593865, "179": 7689630, "180": 7886244, "181": 7984165, "182": 8130747, "183": 8253888, "184": 8403448, "185": 8523897, "186": 8684853, "187": 8802826, "188": 8949612, "189": 9105537, "190": 9267595, "191": 9376656, "192": 9574704, "193": 9686065, "194": 9827097, "195": 9997134, "196": 10174780, "197": 10290813, "198": 10493367, "199": 10611772, "200": 10813692}

k = input().strip()
print(a[k])