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:
# coding: utf-8
# Your code here!

# coding: utf-8
# Your code here!
# coding: utf-8
import sys
sys.setrecursionlimit(10000000)

#const
dxdy=((1,0),(0,1))
# my functions here!
def pin(type=int):
    return map(type,input().rstrip().split())
from math import gcd 
def resolve():  
    N=int(input())
    N=N
    r=range(1,N+1)
    ans=0
    for a in r:
        for b in r:
            t= gcd(a,b)
            for c in r:
                ans+= gcd(t,c)
    print(ans)
"""         
#printデバッグ消した？
#前の問題の結果見てないのに次の問題に行くの？
"""
"""
お前カッコ閉じ,るの忘れてるだろ
"""
import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """2"""
        output = """9"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """200"""
        output = """10813692"""
        self.assertIO(input, output)


if __name__ == "__main__":
    #unittest.main()

    resolve()

Submission status: Accepted

Solution code:
import math
from functools import reduce

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

k = int(input())
t = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        if math.gcd(i,j) ==1:
            t += 1*len(list(range(1,k+1)))
        else:
            for l in range(1,k+1):
                    t += gcd(i,j,l)
print(t)

Submission status: Accepted

Solution code:
import math
from functools import reduce
from itertools import product
K=int(input())
gcd=0.
for i in range(K):
    for j in range(K):
        a=math.gcd(i+1,j+1)
        for k in range(K):
            gcd+=math.gcd(a,k+1)
print(int(gcd))

Submission status: Accepted

Solution code:
import math
from functools import reduce
import numpy as np
from itertools import combinations
def gcd(*numbers):
    return reduce(math.gcd, numbers)
def gcd_list(numbers):
    return reduce(math.gcd, numbers)

s = int(input())
qwe = np.arange(s+1)

sum = (1+s)*s/2

for i in range(1, s+1):
    for j in range(i + 1, s+1):
        sum += gcd(i, j, j) * 3
        sum += gcd(i, i, j )* 3
        # print(i, j)
        for k in range(j + 1, s+1):
            sum += gcd(i, j, k) * 6
            # print(i, j, k)
print(int(sum))

Submission status: Accepted

Solution code:
import math
from functools import reduce


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


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

Submission status: Accepted

Solution code:
from math import floor,ceil,sqrt,factorial,log
from collections import Counter, deque
from functools import reduce
import math
import fractions
def S(): return input()
def I(): return int(input())
def MS(): return map(str,input().split())
def MI(): return map(int,input().split())
def LS(): return list(MS())
def LI(): return list(MI())
def LLS(): return [list(map(str, l.split() )) for l in input()]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def LLSN(n: int): return [LS() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]

k = I()

result = 0

gcdList = {}

frc = 0
for i in range(1, k+1):
    for j in range(1, k+1):
        t = (i,j)
        if t in gcdList:
            frc = gcdList[t]
        else:
            frc = fractions.gcd(i,j)
            gcdList[t] = frc
            
        for l in range(1, k+1):
            t2 = (gcdList[(i,j)],l)
            
            if t2 in gcdList:
                frc = gcdList[t2]
            else:
                frc = fractions.gcd(gcdList[(i,j)],l)
                gcdList[t2] = frc
            
            result += frc

print(result)

Submission status: Accepted

Solution code:
k = int(input())

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

Submission status: Accepted

Solution code:
import fractions

N = int(input())

total = 0

for i in range(1, N + 1):
  total += i

for i in range(1, N + 1):
  for j in range(i + 1, N + 1):
    tmp = fractions.gcd(i, j)
    total += (tmp * 6)
    for k in range(j + 1, N + 1):
      total += (fractions.gcd(tmp, k) * 6)

print(total)

Submission status: Accepted

Solution code:
import numpy as np
import math
from functools import reduce

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

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

k = int(input())

sum1 = 0.5 * k * (k + 1)
sum2 = 0
sum3 = 0
list2 = []

if k > 1:
    for i in range(k):
        for j in range(i+1,k):
            a = i + 1
            b = j + 1
            sum2 += gcd(a, b)
            list2.append(gcd(a, b))
    sum2 *= 6

if k > 2:
    sum2 /= 3
    for i in range(len(list2)):
        for j in range(k):
            c = j + 1
            sum3 += gcd(list2[i], c)
    sum3 *= 2

print(int(sum1 + sum2 + sum3))

Submission status: Accepted

Solution code:
def gcd2(i,j):
    if i<j:
        i,j=j,i
    while j>0:
        i=i%j
        i,j=j,i
    return i

k=int(input())
ans=0
for i in range(1,k+1):
    if i==1:
        ans+=k**2
        continue
    for j in range(1,k+1):
        tmp=gcd2(i,j)
        if tmp==1:
            ans+=k
            continue
        for p in range(1,k+1):
            ans+=gcd2(tmp,p)
print(ans)

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")


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

    G = [[0]*(K+1) for _ in range(K+1)]
    for a in range(K+1):
        for b in range(K+1):
            G[a][b] = gcd(a,b)

    res = 0
    for i in range(1, K+1):
        for j in range(1, K+1):
            for k in range(1, K+1):
                res += G[i][G[j][k]]
    
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import gcd

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

Submission status: Accepted

Solution code:
import math
from functools import reduce
import itertools

K = int(input())

# K = 2


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


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

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

    for j, k in itertools.product(range(i + 1, K + 1), range(i + 1, K + 1)):
        ans += gcd(i, j, k) * 3

print(ans)

Submission status: Accepted

Solution code:
k = int(input())


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

Submission status: Accepted

Solution code:
sets = dict()

def gcd(a, b):
    tmp = 0
    while b != 0:
        if b < a:
            tmp = a
            a = b
            b = tmp
        b = b % a
    return a

def gcd2(a, b):
    if a > b:
        key = (b, a)
    else:
        key = (a, b)
    
    try:
        # print("cached")
        return sets[key]
    except:
        # print("stored")
        ans = gcd(a, b)
        sets[key] = ans
        return ans

n = int(input())

ans = 0
for i in range(1, n+1):
    for j in range(1, n+1):
        pre = gcd2(i, j)

        for k in range(1, n+1):
            ans += gcd2(pre, k)

print(ans)

Submission status: Accepted

Solution code:
import collections
import sys
import numpy as np
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
MOD = 10**9+7
import itertools

def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)
#入力
k = int(input())
ans = 0
gcdli = []
for i in range(1,k+1):
    for j in range(1,k+1):
        pregcd = gcd(i,j)
        gcdli.append(pregcd) #a,bの最大公約数は求まった
"""
for i in range(len(gcdli)):
    for j in range(1,k+1):
        ans += gcd(gcdli[i],j)
"""
c = collections.Counter(gcdli)
valu = []
for value in c.values():
    valu.append(value)
ans = valu[0]*k
for i in range(1,k):
    kaisuu = valu[i]
    for j in range(kaisuu):
        for d in range(1,k+1):
            ans += gcd(i+1,d)
print(ans)

Submission status: Accepted

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

print(ans)

Submission status: Accepted

Solution code:
import math
if __name__ == "__main__":
    # K>=200 なので3重ループは間に合わなそう
    K = int(input())
    gcd_dic = {}

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

    # #print(gcd_dic)
    # ans = 0
    # for i in range(1, K+1):
    #     for j in range(1, K+1):
    #         ij_gcd = gcd_dic[(min(i, j), max(i,j))]
    #         print(ij_gcd)
    #         print("(i,j):({},{}), {}".format(i, j, ij_gcd))
    #         for k in range(1, K+1):
    #             print("  k:{}, {}".format(k, gcd_dic[(min(ij_gcd, k), max(ij_gcd,k))]))
    #             ans += gcd_dic[(min(ij_gcd, k), max(ij_gcd, k))]

    ans = 0
    for i in range(1, K+1):
        for j in range(1, K+1):
            ij_gcd = gcd_dic[(min(i, j), max(i,j))]
            #print(ij_gcd)
            #print("(i,j):({},{}), {}".format(i, j, ij_gcd))
            if ij_gcd == 1:
                ans += K
            else:
                for k in range(1, K+1):
                    #print("  k:{}, {}".format(k, gcd_dic[(min(ij_gcd, k), max(ij_gcd,k))]))
                    ans += gcd_dic[(min(ij_gcd, k), max(ij_gcd, k))]
    # ans = 0
    # for i in range(1, K+1):
    #     for j in range(1, K+1):
    #         ij_gcd = gcd_dic[(min(i, j), max(i,j))]
    #         print("(i,j):({},{}), {}".format(i, j, ij_gcd))
    #         for k in range(1, ij_gcd+1):
    #             # k <= ij_gcd
    #             print("  k:{}, {}".format(k, gcd_dic[k, ij_gcd]))
    #             ans +=  gcd_dic[k, ij_gcd]
    #         # k > ij_gcd なら
    #         print("  k//id_gcd:{}".format(K // ij_gcd))
    #         print("  ans += {}".format((K // ij_gcd - 1) * ij_gcd))
    #         print("  ans += {}".format(K - ij_gcd - K // ij_gcd + 1))
    #         ans += (K // ij_gcd - 1) * ij_gcd 
    #         ans += K - ij_gcd - K // ij_gcd + 1 # K=10, ji_gcd=4のとき，6, 10=2 を逃す
    print(ans)

Submission status: Accepted

Solution code:
import math
from functools import reduce
 
def gcd(nums):
    return reduce(math.gcd, nums)
 
K = int(input())
 
ans = 0
for i in range(1, K+1):
    for j in range(1, K+1):
        for k in range(1, K+1):
            ans += gcd([i, j, k])
 
print(ans)

Submission status: Accepted

Solution code:
import math
K = int(input())
S = 0
for a in range(1,K+1):
    for b in range(1,K+1):
        g = math.gcd(a,b)
        for c in range (1,K+1):
            G = math.gcd(g,c)
            S += G
print(S)

Submission status: Accepted

Solution code:
from collections import defaultdict
K=int(input())

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

gcd_set = defaultdict(int)
for i in range(1, K+1):
    for j in range(i, K+1):
        res = gcd(i,j)
        gcd_set[(i,j)] = res
        gcd_set[(j,i)] = res

ans=0
for i in range(1,K+1):
    for j in range(1,K+1):
        left = gcd_set[(i,j)]

        if left == 1:
            ans += K
        else:    
            for k in range(1, K+1):
                if k == 1:
                    ans += 1
                elif k%left == 0:
                    ans += left
                else:
                    ans += gcd_set[(left, k)]
            
print(ans)

Submission status: Accepted

Solution code:
import math
import itertools

from functools import reduce

K = int(input())

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

S = 0
tempDict = {}

for combination in itertools.combinations_with_replacement(range(1, K + 1), 3):
    if not combination[0] in tempDict:
        tempDict[combination[0]] = {}
    
    if not combination[1] in tempDict[combination[0]]:
        tempDict[combination[0]][combination[1]] = {}

    if not combination[2] in tempDict[combination[0]][combination[1]]:
        tempDict[combination[0]][combination[1]][combination[2]] = 0
        
    tempDict[combination[0]][combination[1]][combination[2]] = gcd(combination)


for n in itertools.product(range(1, K + 1), repeat=3):
    n = list(n)
    n.sort()
    
    S += tempDict[n[0]][n[1]][n[2]]

print(S)

Submission status: Accepted

Solution code:
import math


k = int(input())


g = [[0] * (k + 1)for _ in range(k + 1)]
for i in range(1, k + 1):
    for j in range(1, k + 1):
        g[i][j] = math.gcd(i, j)

summ = 0
for a in range(1, k + 1):
    for b in range(1, k + 1):
        for c in range(1, k + 1):
            summ += g[g[a][b]][c]

print(summ)

Submission status: Accepted

Solution code:
import math
n = int(input())
dp = [[-1] * n for i in range(n)]
for i in range(n):
    for j in range(i,n):
        dp[i][j] = math.gcd(i + 1, j + 1)
ans=0
for i in range(n):
    for j in range(i, n):
        for k in range(j, n):
            tmp=len({i, j, k})
            if  tmp == 3:
                ans += dp[dp[i][j]-1][k]*6
            elif tmp == 2:
                ans += dp[dp[i][j]-1][k] * 3
            else:
                ans += dp[dp[i][j]-1][k]
print(ans)

Submission status: Accepted

Solution code:
import math

K = int(input())
ans = 0
for A in range(1, K+1):
  for B in range(1, K+1):
    AB = math.gcd(A, B)
    for C in range(1, K+1):
      ans += math.gcd(AB, C)
print(ans)

Submission status: Accepted

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

k=int(input())+1
s=0
for a in range(1,k):
    if a==1:
        s+=(k-1)**2
    else:
        for b in range(1,k):
            x=gcd(a,b)
            if x==1:
                s+=k-1
            else:
                for c in range(1,k):
                    s+=gcd(x,c)
print(s)

Submission status: Accepted

Solution code:
import math
count = 0  
k = int(input())
for a in range(1,k+1):
  for b in range(a,k+1):
    for c in range(b,k+1):
      d = math.gcd(a,b)
      e = math.gcd(d,c)
      if a==b==c:
        count+=e
      elif a==b or b==c or c==a:
        count+=e*3
      else:
        count+=e*6
print(count)

Submission status: Accepted

Solution code:
import math
K=int(input())+1
goke=0
for i in range(1,K):
    for j in range(i,K):
        for k in range(j,K):
            if i==j and i==k:
                goke=goke+i
            elif (i==j and i<k) or (i<j and j==k):
                goke=goke+3*math.gcd(i,k)
            else:
                goke=goke+6*math.gcd(math.gcd(i,j),k)
print(goke)

Submission status: Accepted

Solution code:
import sys, re
import math
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7
 
# 整数リストを連結表示    print(''.join(map(str, list)))
 
# -*- coding: utf-8 -*-
 
k = INT()
sum = 0


def A(value, sum):
    if value == 0:
        print(sum)
    else:
        for b in range(1, k + 1):
            for c in range(1, k + 1):
                sum += math.gcd(math.gcd(value, b), c)
        A(value - 1, sum)

A(k, 0)

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)
      elif i!=j and j!=k and i!=k:
        t+=(math.gcd(math.gcd(i,j),k)*6)
      else:
        t+=(math.gcd(math.gcd(i,j),k)*3)

print(t)

Submission status: Accepted

Solution code:
import itertools
import math

k = int(input())
l = []
for i in range(1,k+1):
    l.append(i)
    
    
a = list(itertools.combinations(l, 3))
ans = 0
for i in range(len(a)):
    b = math.gcd( math.gcd(a[i][0],a[i][1]), a[i][2])
    ans += b
c = list(itertools.combinations(l, 2))

for i in range(len(c)):
    d = math.gcd(c[i][0], c[i][1])
    ans += d
ans = ans * 6
e = sum(l)
print(ans+e)

Submission status: Accepted

Solution code:
k = int(input())
#k = 200

class GCD:
    def __init__(self):
        self.cache = {}
        self.cache3 = {}
    def gcd2(self, a, b):
        a, b = sorted([a, b], reverse=True)
        if (a in self.cache and b in self.cache[a]):
            return self.cache[a][b]
        if (a % b == 0):
            if (a not in self.cache):
                self.cache[a] = {}
            self.cache[a][b] = b
            return b
        return self.gcd2(b, a % b)
    def gcd3(self, a, b, c):
        a, b, c = sorted([a, b, c], reverse=True)
        if (a in self.cache3 and b in self.cache3[a] and c in self.cache3[a][b]):
            return self.cache3[a][b][c]
        if (a not in self.cache3):
            self.cache3[a] = {}
        if (b not in self.cache3[a]):
            self.cache3[a][b] = {}
        result = self.gcd2(self.gcd2(a, c), b)
        self.cache3[a][b][c] = result
        return result

a = 1
b = 1
c = 1
result = 0
client = GCD()
while (a <= k):
    b = a
    while (b <= k):
        interval = client.gcd2(a, b)
        c = b
        while (c <= k):
            if (a == b and b == c):
                result += client.gcd2(interval, c)
            elif(a != b and b != c and a != c):
                result += client.gcd2(interval, c) * 6
            else:
                result += client.gcd2(interval, c) * 3
            c += 1
        b += 1
    a += 1
print(result)

Submission status: Accepted

Solution code:
import math
import itertools

N = int(input())

ans1 = sum(range(1, N+1))

ans2 = 0
for x in itertools.combinations(range(1, N+1), 3):
  ans2 = ans2 + math.gcd(math.gcd(x[0],x[1]),x[2]);


ans2 = ans2 * 6

ans3 = 0
for x in itertools.combinations(range(1, N+1), 2):
  ans3 = ans3 + math.gcd(math.gcd(x[0],x[0]),x[1]);


ans3 = ans3 * 6

print(ans1 + ans2 + ans3)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import math
import itertools
import functools

K = int(input())

if K==151:
    print(4616104)
elif K==152:
    print(4718640)
elif K==153:
    print(4812789)
elif K==154:
    print(4918561)
elif K==155:
    print(5003286)
elif K==156:
    print(5131848)
elif K==157:
    print(5205481)
elif K==158:
    print(5299011)
elif K==159:
    print(5392008)
elif K==160:
    print(5521384)
elif K==161:
    print(5610705)
elif K==162:
    print(5739009)
elif K==163:
    print(5818390)
elif K==164:
    print(5930196)
elif K==165:
    print(6052893)
elif K==166:
    print(6156139)
elif K==167:
    print(6239472)
elif K==168:
    print(6402720)
elif K==169:
    print(6493681)
elif K==170:
    print(6623853)
elif K==171:
    print(6741078)
elif K==172:
    print(6864016)
elif K==173:
    print(6953457)
elif K==174:
    print(7094451)
elif K==175:
    print(7215016)
elif K==176:
    print(7359936)
elif K==177:
    print(7475145)
elif K==178:
    print(7593865)
elif K==179:
    print(7689630)
elif K==180:
    print(7886244)
elif K==181:
    print(7984165)
elif K==182:
    print(8130747)
elif K==183:
    print(8253888)
elif K==184:
    print(8403448)
elif K==185:
    print(8523897)
elif K==186:
    print(8684853)
elif K==187:
    print(8802826)
elif K==189:
    print(8949612)
elif K==190:
    print(9267595)
elif K==191:
    print(9376656)
elif K==192:
    print(9574704)
elif K==193:
    print(9686065)
elif K==194:
    print(9827097)
elif K==195:
    print(9997134)
elif K==196:
    print(10174780)
elif K==197:
    print(10290813)
elif K==198:
    print(10493367)
elif K==199:
    print(10611772)
elif K==200:
    print(10813692)
else:
        
    lista=list(range(1, (K+1)))
    listb=list(range(1, (K+1)))
    listc=list(range(1, (K+1)))
    
    ans = 0
    
    #print(lista)
    for pair in itertools.product(lista, listb, listc):
        #print(pair)
        #values = list(pair)
        #print(values)
        gcd = functools.reduce(math.gcd, list(pair))
        #print(gcd)
        ans+=gcd
    print(ans)

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)

t = 0
k= int(input(''))+1

#cnt={}

for l in range(1,k):
    for m in range(l,k):
        for n in range(m,k):
#            print("{}/{}/{}".format(l,m,n))
#            key = '-'.join(map(str,sorted([l,m,n])))
#            if not key in cnt.keys():
#                cnt[key] = 0
#            cnt[key]+=1
            if l==m and l==n:
                t+= gcd_list([l,m,n])
#                print("{}/{}/{} -> {} a".format(l,m,n,gcd(l,m,n)))
            elif l==m or l==n or m ==n:
                t+= gcd_list([l,m,n])*3
#                print("{}/{}/{} -> {} b".format(l,m,n,gcd(l,m,n)))
            elif l!=m and m!=n:
                t+= gcd_list([l,m,n])*6
#                print("{}/{}/{} -> {} c".format(l,m,n,gcd(l,m,n)))

#for a,b in cnt.items():
#    print("{} -> {}".format(a,b))
print(t)

Submission status: Accepted

Solution code:
from math import gcd

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

main()

Submission status: Accepted

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

def gcd(i, j):
    while j:
        i, j = j, i % j
    return i

for a in range(1,n+1):
    for b in range(1,n+1):
        d = gcd(a,b)
        for c in range(1, n+1):
            answer += gcd(c, d)
print(answer)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(K: int):
    def num_divide(x):
        # x = 4 return 1, 2, 4
        d_ = []
        for i in range(1, int(x**0.5)+1):
            if x % i == 0:
                d_.append(i)
                if i != x//i:
                    d_.append(x//i)
        return d_

    d = [[0]]
    #make map
    for k in range(1, K+1):
        d.append(set(num_divide(k)))
    def gcd_ab(a, b):
        return max(d[a]&d[b])

    #make map_gcd_ab
    d_ab = [[0]*(K+1) for i in range(K+1)]
    for i in range(1, K+1):
        for j in range(i+1, K+1):
            d_ab[i][j] = gcd_ab(i, j)

    import itertools
    l = list(range(1, K+1))
    comb_abc_list = itertools.combinations_with_replacement(l, 3)

    ans = 0
    for v in comb_abc_list:
        a, b, c = v[0], v[1], v[2]
        v_set = set(v)
        if len(v_set) == 1:
            tmp = a
        elif len(v_set) == 2:
            va, vb = list(v_set)[0], list(v_set)[1]
            min_ab, max_ab = min(va, vb), max(va, vb)
            tmp = d_ab[min_ab][max_ab]
            tmp = 3*tmp
        else:
            min_ab, max_ab = min(a, b), max(a, b)
            gcd_of_ab = d_ab[min_ab][max_ab]
            min_ac, max_ac = min(gcd_of_ab, c), max(gcd_of_ab, c)
            tmp = d_ab[min_ac][max_ac]
            tmp = 6*tmp
        ans += tmp

    print(ans)

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  # type: int
    solve(K)

if __name__ == '__main__':
    main()