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())
num = 0

for a in range(K):
    for b in range(K):
        ab = math.gcd(a+1, b+1)
        for c in range(K):
            num += math.gcd(ab, c+1)

print(num)

Submission status: Accepted

Solution code:
n = int(input())
total = 0

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

	return gcd(b, a % b)

total = total + n * (n+1) / 2

for i in range(n):
	for j in range(i+1,n):
		total = total + 6 * gcd(j+1,i+1)

for i in range(n):
	for j in range(i+1,n):
		for k in range(j+1,n):
			l = gcd(j+1,k+1)
			if i < l:
				total = total + 6 * gcd(l,i+1)
			else:
				total = total + 6 * gcd(i+1,l)

print(int(total))

Submission status: Accepted

Solution code:
import sys
mod = pow(10, 9) + 7
sys.setrecursionlimit(pow(10, 8))

def power(x, y):
    if   y == 0: return 1
    elif y == 1	 : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else: return power(x, (y-1)//2)**2 * x % mod
    
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def div(a, b):
    return mul(a, power(b, mod-2))
def div2(a, b):
    return mul(a, modinv(b))

def modinv(a):
    b, u, v = mod, 1, 0
    while b:
        t = a//b
        a, u = a-t*b, u-t*v
        a, b, u, v = b, a, v, u
    u %= mod
    return u

def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r]
K, = map(int, input().split())
N = 3
B = [0] * (K+1)
r = 0
for i in range(K, 0, -1):
    ac = K//i
    c = power(ac, N)
    bsum = 0
    for j in range(ac-1):
        j += 2
        bsum += B[i*j]
    B[i] = (c - bsum)%mod
    r = (r+B[i]*i)%mod
print(r)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import math
from functools import lru_cache

# prime_200 = {
#     2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
#     73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
#     179, 181, 191, 193, 197, 199
# }

@lru_cache(maxsize=None)
def get_gcd(a, b):
    return math.gcd(a, b)


def main():
    k = int(input().strip())
    sum = 0

    # すべて同じ(a, a, a)
    sum += k * (k + 1) // 2

    # 2 つ同じ（a, a, b）
    for a in range(1, k + 1):
        # if a in prime_200:
        #     sum += 3 * (k - 1)  # 自分と同じを除く分 * 3c1
        #     continue
        for b in range(1, k + 1):
            if a == b:
                continue  # 同じは除く
            # if b in prime_200:
            #     sum += 3  # b が素数なら gcd は 1 * 3c1
            #     continue
            a_, b_ = (a, b) if a < b else (b, a)
            sum += 3 * get_gcd(a_, b_)

    # 3 つ違う (a, b, c)
    for a in range(1, k + 1):
        for b in range(a + 1, k + 1):
            if a == b:
                continue
            a_b_ = get_gcd(a, b)
            for c in range(b + 1, k + 1):
                if a == c or b == c:
                    continue
                sum += 6 * get_gcd(a_b_, c)
    print(sum)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
k = int(input())
ans = {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}
print(ans[k])

Submission status: Accepted

Solution code:
import math
from functools import reduce

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

K = int(input())
ans = 0
memo = {}

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:
import math
K = int(input())
s = 0
c = dict()
for a in range(1, K+1):
    for b in range(1, K+1):
        ab = math.gcd(a, b)
        if ab == 1:
            s += K
        else:
            for c in range(1, K+1):
                s += math.gcd(ab, c)
print(s)

Submission status: Accepted

Solution code:
import time
start = time.time()

import math
from functools import reduce

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

K =int(input())

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

print(suma)

Submission status: Accepted

Solution code:
#『aとbとcの最大公約数』　＝　『aとbの最大公約数』と『c』　の最大公約数
K = int(input())
K = K+1
from fractions import gcd
ans =0
gcd_memo = [[[] for k in range(201)] for i in range(201)]
for i in range(201):
    for k in range(201):
        val = gcd(i,k)
        gcd_memo[i][k] = val
        gcd_memo[k][i] = val

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
K=int(input())
L1=[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(L1[K-1])

Submission status: Accepted

Solution code:
import math

k = int(input())
print(sum(math.gcd(math.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)))

Submission status: Accepted

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

n = int(input())

ans = 0

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

for i in range(1,n):
    for j in range(i+1,n+1):
        ans += 6*gcd(i,j)
# print(ans)
ans += (n*(n+1))//2

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

Submission status: Accepted

Solution code:
import math 

K  = int(input())
total  = 0

for s in range(1,K+1):
    for t in range(1,K+1):
        alpha = math.gcd(s,t)
        if alpha == 1:
            total += K
            continue
        for u in range(1,K+1):
            # print(s,t,u,math.gcd(alpha,u))
            total +=math.gcd(alpha,u)

print(total)

Submission status: Accepted

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


a = 0
k = int(input())
for i in range(1,k+1):
    for j in range (i,k+1):
        for l in range(j,k+1):
            g = gcd(i,j,l)
            if i==j and j==l:
                a = a+g
            elif i != j and j != l and l != i:
                a = a+ (6*g)
            else:
                a = a + (3*g)
print(a)

Submission status: Accepted

Solution code:
import math
 
n=int(input())+1
ans=0
for i in range(1,n):
  for j in range(i,n):
    for k in range(j,n):
      if i==j and i==k:
        buff=1
      elif i==j:
        buff=3
      elif j==k:
        buff=3
      else:
        buff=6
      g1=math.gcd(i,j)
      g=math.gcd(k,g1)
      ans+=g*buff
print(ans)

Submission status: Accepted

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


resolve()

Submission status: Accepted

Solution code:
# import math
# from functools import lru_cache

# @lru_cache(maxsize=100000)
# def gcd_list(a, b, c):
#     return gcd(gcd(a, b), c)

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


# for k in range (1, 201):
#     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("%d:%d," % (k, ans))


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 = int(input())
print(a[k])

Submission status: Accepted

Solution code:
import math
from functools import reduce

k = int(input())

def gcd2(*numbers):
    return reduce(math.gcd,numbers)
sum = 0
for a in range(1,k+1):
    for b in range(a,k+1):
        for c in range(b,k+1):
            if len(set([a,b,c]))==2:
                sum = sum + gcd2(a,b,c)*3
            elif len(set([a,b,c]))==1:
                sum = sum + gcd2(a,b,c)
            else:
                sum = sum + gcd2(a,b,c)*6
            #print(gcd2(a,b,c))


print(sum)

Submission status: Accepted

Solution code:
from math import gcd

n = int(input())
ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
g = [[-1]*n for _ in range(n)]

import fractions

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

ans = 0
for i in range(n):
  for j in range(n):
    for k in range(n):
      a, b, c = i+1, j+1, k+1
      ab_gcd = g[a-1][b-1]
      abc_gcd = g[ab_gcd-1][c-1]
      ans += abc_gcd
      
print(ans)

Submission status: Accepted

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

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

n = int(input())
ans = n * (n+1) //2
for i in range(1,n+1):
    for j in range(i+1,n+1):
        ans += gcd(i,j) * 6
if n >2:
    for i in range(1,n+1):
        for j in range(i+1,n+1):
            for k in range(j+1,n+1):
                ans += gccd(i,j,k) * 6
print(ans)

Submission status: Accepted

Solution code:
import math
import itertools
from functools import reduce

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

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

def main():
    K=int(input())
    #l=[i for i in range(1,K+1)]
    ans=0
    dp=[[[None for i in range(201)] for j in range(201)] for k in range(201)]

    for i in range(1,K+1):
        for j in range(1,K+1):
            for k in range(1,K+1):
                p=sorted([i,j,k])
                if dp[p[0]][p[1]][p[2]] == None:
                    tmp=gcd(i,j,k)
                    dp[p[0]][p[1]][p[2]] = tmp
                    ans+=tmp
                else:
                    ans+= dp[p[0]][p[1]][p[2]]
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
K=int(input())
count=0
for t in range(1,K+1):
    for s in range(t,K+1):
        for v in range(s,K+1):
            if t!=s!=v:
                count+=(6*math.gcd((math.gcd(t,s)),v))
            elif (t==s and t!=v) or (t==v and t!=s)or (s==v and s!=t):
                count+=(3*math.gcd((math.gcd(t,s)),v))
            else:
                count+=math.gcd((math.gcd(t,s)),v)
print(count)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def gcd(x, y):
    while y != 0:
        (x, y) = (y, x % y)
    return x
N = int(input())

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

Submission status: Accepted

Solution code:
k = int(input())

import math


# a=b=c
# from 1 to  k  => (1+k)*k/2
ans = k * (k + 1) // 2

# a, b=c
# gcd(a,b)
for a in range(1, k):
    for b in range(a+1, k+1):
        ans += 3*2*math.gcd(a, b)

# a,b,c
for a in range(1, k-1):
    for b in range(a+1, k):
        for c in range(b+1, k+1):
            ans += 3*2*math.gcd(a, math.gcd(b, c))

print(ans)

Submission status: Accepted

Solution code:
import math

k=int(input())

sum=0
sum1=0
sum2=0
sum3=0
for a in range(1,k+1):
    sum1+=a
sum+=sum1
for a in range(1,k+1):
    for b in range(a+1,k+1):
        ans=a
        ans=math.gcd(ans,b)
        sum2+=ans
sum+=sum2*6
for a in range(1,k+1):
    for b in range(a+1,k+1):
        for c in range(b+1,k+1):
            ans=a
            ans=math.gcd(ans,b)
            ans=math.gcd(ans,c)
            sum3+=ans
sum+=sum3*6

print(sum)

Submission status: Accepted

Solution code:
import math
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):
			A=math.gcd(math.gcd(a,b),c)
			if a==b and b==c:
				ans+=A
			elif a==b or b==c:
				ans+=(A*3)
			else:
				ans+=(A*6)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

import math
from functools import reduce

n = int(input())
def gcd(*numbers):
    return reduce(math.gcd, numbers)
  
ans = 0

for a in range(1, n+1):
  for b in range(1, n+1):
      tmp = gcd(a, b)
      if not tmp == 1:
          for c in range(1, n+1):
               tmp2 = gcd(tmp, c)
               ans = ans + tmp2
      else:
          ans = ans + 1 * n
print(ans)

Submission status: Accepted

Solution code:
import math
import itertools

def solve(k):
  if k == 1:
    return 1
  if k == 2:
    return 9

  ans = 0
  x = [i for i in range(1, k+1)]
  for a, b, c in itertools.combinations(x, 3):
    ans += 6*math.gcd(math.gcd(a,b), c)

  for a,b in itertools.combinations(x, 2):
    ans += 6*math.gcd(a,b)

  ans += k*(k+1)/2
  return int(ans)

if __name__ == "__main__":
  k = int(input())
  print(solve(k))

Submission status: Accepted

Solution code:
import math
from functools import reduce

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

N = int(input())
ans = 0
"""
memo = {}
for i in range(1,N+1):
    for j in range(1,N+1):
        for k in range(1,N+1):
            key = "&".join(map(str,sorted([i,j,k])))
            m = memo.get(key)
            if(m):
                ans += m
            else:
                gcdnum = gcd(i,j,k)
                ans += gcdnum
                memo[key] = gcdnum
"""
memo = {}
for i in range(1,N+1):
    for j in range(1,N+1):
        tmp = gcd(i,j)
        for k in range(1,N+1):
            ans += gcd(tmp,k)
                
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
#import time
def gcd(a,b,c):
    return math.gcd(a,math.gcd(b,c))
#time1=time.time()
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):
            if i==j and j==k:
                ans+=gcd(i,j,k)
            elif i==j or i==k or j==k:
                ans+=3*gcd(i,j,k)
            else:
                ans+=6*gcd(i,j,k)
#time2=time.time()
print(ans)
#print(time2-time1)

Submission status: Accepted

Solution code:

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]

K=int(input())


print(l[K-1])

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n = int(input())
ans = 0
# gcd_grid = [[0] * 201 for _ in range(201)]


def gcd(n, m):
    """if n <= 200 and m <= 200:
        if gcd_grid[n][m] != 0:
            return gcd_grid[n][m]"""
    a, b = n, m
    if a > b:
        a, b = b, a
    while a != 0:
        a, b = b % a, a
    # gcd_grid[n][m] = b
    # gcd_grid[m][n] = b
    return b


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

Submission status: Accepted

Solution code:
k = int(input())
ary = [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(ary[k-1])

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import math as mt

num = int(input())
list = []

for i in range(1, num+1):
    for j in range(1, num+1):
        for k in range(1, num+1):
            twoGcd = mt.gcd(i, j)
            threeGcd = mt.gcd(twoGcd, k)
            list.append(threeGcd)
            
print(sum(list))

Submission status: Accepted

Solution code:
from itertools import *

def yuc(a,b):
  c=a%b
  while c!=0:
    a=b
    b=c
    c=a%b
  return b

n=int(input())
ar=list(range(1,n+1))
ans=0

for tup in combinations_with_replacement(ar,3):
  if tup[0]==tup[1]==tup[2]:
    ans+=tup[0]
  elif tup[0]==tup[1]:
    ans+=3*yuc(tup[0],tup[2])
  elif tup[1]==tup[2]:
    ans+=3*yuc(tup[0],tup[1])
  elif tup[0]==tup[2]:
    ans+=3*yuc(tup[0],tup[1])
  else:
    ans+=6*yuc(tup[0],yuc(tup[1],tup[2]))
print(ans)

Submission status: Accepted

Solution code:
import math
from functools import reduce
import itertools


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


k = int(input())
items = list(range(1, k+1))
ans = sum(items)
ans += sum([6 * gcd_list(item) for item in itertools.combinations(items, 2)])
ans += sum([6 * gcd_list(item) for item in itertools.combinations(items, 3)])

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
 
K = int(input())
ans = 0

gcd2 = np.zeros((K+1, K+1), dtype=int)

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

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

for i in range(1, K):
    for j in range(i+1, K+1):
        ans += 3 * gcd2[i,j]
for i in range(1, K+1):
    for j in range(1, i):
        ans += 3 * gcd2[i,j]
        
for i in range(1, K-1):
    for j in range(i+1, K):
        for k in range(j+1, K+1):
            ans += 6 * gcd2[i,gcd2[j,k]]
            
print(ans)

Submission status: Accepted

Solution code:
import math

K = int(input())
ans = 0
for a in list(range(1, K+1)):
    for b in list(range(1, a+1)):
        for c in list(range(1, b+1)):
            a_b = math.gcd(a, b)
            a_b_c = math.gcd(a_b, c)
            if a == b == c:
                ans = ans + a_b_c
            elif a != b and b != c and a != c:
                ans = ans + a_b_c * 6
            else:
                ans = ans + a_b_c * 3

print(ans)

Submission status: Accepted

Solution code:
import math
k = int(input())
a = (k+1)*k/2
b = 0
for i in range(1,k-1):
    for j in range(i+1,k):
        for l in range(j+1,k+1):
            b += math.gcd(math.gcd(i,j),l)
b = b*6
c = 0
for i in range(1,k):
    for j in range(i+1,k+1):
        c += math.gcd(i,j)
c = c*6
print(int(a+b+c))

Submission status: Accepted

Solution code:
import math
from functools import reduce

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

Submission status: Accepted

Solution code:
import math
from functools import reduce


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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

K = int(input())
GCD = [ k for k in range(1, K+1)]
output = []

for v in combinations_with_replacement(GCD, 3):
    if len(set(v))==2:
        bi = 3
    elif len(set(v))==3:
        bi = 6
    else:
        bi = 1
    output.append(gcd(list(v))*bi)
print(sum(output))

Submission status: Accepted

Solution code:
import math
K = int(input())
cnt = 0
tmp = 0
for a in range(1, K+1):
    for b in range(1, a+1):
        for c in range(1, b+1):
            if a==b==c:
                tmp = math.gcd(a, b)
                cnt += math.gcd(tmp, c)
            elif a!=b!=c!=a:
                tmp = math.gcd(a, b)
                cnt += 6*math.gcd(tmp, c)
            else:
                tmp = math.gcd(a, b)
                cnt += 3*math.gcd(tmp, c)

print(cnt)

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 i==k:
                ans += gcd(i,j,k)*3
            else:
                ans += gcd(i,j,k)*6

print(ans)