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 sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols
    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])
    return ret


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_map_as_int(H):
    '''
    #→1,.→0として読み込む
    '''
    ret = []
    for _ in range(H):
        ret.append([1 if s == '#' else 0 for s in read()[:-1]])
        # 内包表記はpypyでは若干遅いことに注意
        # #numpy使うだろうからこれを残しておくけど
    return ret


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations, combinations_with_replacement
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from math import gcd


def lcm(a, b):
    # 最小公倍数
    g = gcd(a, b)
    return a * b // g


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}
# 8000000をgcd愚直は間に合うか？ #3つの順番は入れ替わってもよい
# 埋め込むか
K = read_a_int()
print(ans[K])

Submission status: Accepted

Solution code:
import math

K = int(input())

total = 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):
            abc = math.gcd(ab, c)
            total += abc

print(str(total))

Submission status: Accepted

Solution code:
N = int(input())
import math
from functools import reduce

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

sum = 0
for a in range(1,N+1):
    for b in range(1,N+1):
        for c in range(1,N+1):
            sum += gcd(a, b, c)
print(sum)

Submission status: Accepted

Solution code:
import math

k=int(input())

x=[0]*201

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

ans=0
for i in range(1,201):
    for j in range(1,k+1):
        w=math.gcd(i,j)
        ans+=w*x[i]
print(ans)

Submission status: Accepted

Solution code:
import heapq
from collections import defaultdict, deque
from math import ceil, factorial, gcd
import sys

sys.setrecursionlimit(10 ** 7)
INF = float("inf")
MOD = 10 ** 9 + 7

si = lambda: input().strip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
lmii = lambda: list(map(int, input().split()))
smii = lambda: sorted(map(int, input().split()))


K = ii()

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

print(ans)

Submission status: Accepted

Solution code:
import math

def solve():
    K = int(input())
    sum = 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):
                sum += math.gcd(ab, c)
                pass
    print(sum)


if __name__ == '__main__':
    solve()

Submission status: Accepted

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


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


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

Submission status: Accepted

Solution code:
import math

K = int(input())
# for K in range(201):
#     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,end=',')

print([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]
      [K])

Submission status: Accepted

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

Submission status: Accepted

Solution code:

def gcd_core(a, b):
    if b == 0:
        return a
    else:
        return gcd_core(b, a % b)
def gcd(a,b,c):
    return  gcd_core((gcd_core(a,b)),c)

k = int(input())
al = {}
ans = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        for l in range(1,k+1):
            # tp = [i,j,l]
            # tp.sort()
            # ky = ",".join(map(str,tp))
            # if ky not in al:
            #     val = gcd(i,j,l)
            #     al[ky] = val
            #     ans += val
            # else:
            #     ans += al[ky]
            ans += gcd(i,j,l)

print(ans)

Submission status: Accepted

Solution code:
ans1=[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]
ans2=[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]

ans=ans1+ans2
print(ans[int(input())])

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)
K = int(input())
A = 0
for a in range(K):
  for b in range(K):
    for c in range(K):
      A += gcd(a+1,b+1,c+1)
print(A)

Submission status: Accepted

Solution code:
import math
N = int(input())
ans = 0
temp  = [ [-1] * (N + 1) for _ in range(N + 1)]
for i in range(1,N + 1):
    for j in range(i, N + 1):
        hoge = math.gcd(i,j)
        temp[i][j] =temp[j][i] = hoge


for i in range(1,N + 1):
    for j in range(1, N + 1):
        for k in range(1, N + 1):
            hoge = temp[i][j]
            ans += temp[hoge][k]

print(ans)

Submission status: Accepted

Solution code:
import sys
#import copy
#import numpy as np
#import itertools
#import collections
#from collections import deque
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
#from scipy.sparse import csr_matrix
import functools

sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
#read = sys.stdin.buffer.read

def gcd(nums):
    return functools.reduce(euclid, nums)

def euclid(a, b):
    if b > a:
        a, b = b, a
    if b == 0:
        return a
    else:
        return euclid(b, a%b)

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

    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)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math


def main():
    n = int(input())
    l = [i for i in range(1, n + 1)]

    def gen(l):
        for i in l:
            for j in l:
                for k in l:
                    yield math.gcd(i, math.gcd(j, k))

    return sum(gen(l))


if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
# 最大公約数
from collections import Counter


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


def resolve():
    k = int(input())
    l = [None] * k ** 2
    for i in range(k):
        for j in range(k):
            l[i * k + j] = gcd(i + 1, j + 1)
    c = Counter(l)
    ans = 0
    for key, v in c.items():
        for i in range(k):
            ans += gcd(i + 1, key) * v
    print(ans)


if __name__ == '__main__':
    resolve()

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

print(ans)

Submission status: Accepted

Solution code:
K=int(input())
from math import gcd
s=0
G=[[0 for i in range(K)] for i in range(K)]
for i in range(0,K):
    for j in range(0,K):
        G[i][j]=gcd(i+1,j+1)
for a in range(0, K):
    for b in range(0,K):
        for c in range(0,K):
            s+=G[G[b][c]-1][a]
print(s)

Submission status: Accepted

Solution code:

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
k =  int(input())
ans=0
for i in range(k):
     for j in range(k):
          for h in range(k):
               ans += gcd(gcd(i+1,j+1),h+1)
print(ans)

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
k=int(input())
l=[math.gcd(i,j) for j in range(1,k+1) for i in range(1,k+1)]
o=0
for i in l:
  for j in range(1,k+1):
    o+=math.gcd(i,j)
print(o)

Submission status: Accepted

Solution code:
k = int(input())

if k == 1:
    print(1)
    exit()
elif k == 2:
    print(9)
    exit()

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

ans = 0
for a in range(1, k+1):
    ans += a
    for b in range(a + 1, k+1):
        d = gcd(a, b)
        ans += d * 6
        for c in range(b + 1, k+1):
            ans += gcd(d, c) * 6

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()

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

ret = 0
memo = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, n + 1):
        memo[i][j] = gcd(i, j)


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



print(ret)

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

Submission status: Accepted

Solution code:
from functools import lru_cache
from math import gcd

cgcd = lru_cache(maxsize=None)(gcd)

k = int(input())
ans = 0
for a in range(1, k + 1):
    for b in range(1, k + 1):
        d = cgcd(a, b)
        if d == 1:
            ans += k
            continue
        for c in range(1, k + 1):
            ans += cgcd(d, c)
print(ans)

Submission status: Accepted

Solution code:
import sys, math
def input(): return sys.stdin.readline().strip()


def main():
    K = int(input())
    ans = 0
    add = 0
    for a in range(1, K + 1):
        for b in range(a + 1, K + 1):
            d = math.gcd(a, b)
            add += d
            for c in range(b + 1, K + 1):
                ans += math.gcd(d, c)
    ans *= 6
    ans += add * 6
    ans += K * (K + 1) // 2
    print(ans)

if __name__ == "__main__":
    main()

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(i, gcd(j, l))
print(ans)

Submission status: Accepted

Solution code:
from math import gcd

K = int(input())

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

Submission status: Accepted

Solution code:
def gcd(x,y):
    while(y): 
        x, y = y, x % y 
    return x
    

out = 0
K = int(input())
for i in range(1, K + 1):
    count = K//i
    val = 0
    for j in range(1,i + 1):
        if gcd(i,j) == 1:
            val += 1
    out += val * count * count * count
print(out)

Submission status: Accepted

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

#dp = [[[-1] * 210 for _ in range(210)] for _ in range(210)]
ans = 0
for a in range(1, K+1):
    for b in range(a, K+1):
        for c in range(b, K+1):
            size = len(set([a, b, c]))
            gd = gcd(a, gcd(b, c))
            if size == 1:
                ans += gd
            elif size == 2:
                ans += 3 * gd
            else:
                ans += 6 * gd
print(ans)

Submission status: Accepted

Solution code:
def GCD(a, b):
    if b == 0:
        return a
    else:
        return GCD(b, a % b)

def main():
    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):
                tmp = GCD(i, j)
                ans += GCD(tmp, k)
    print(ans)

    return 0


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from math import gcd
k=int(input())
ans=sum(range(1,k+1))
for a in range(1,k):
    for b in range(a+1,k+1):
        ans+=6*gcd(a,b)
for a in range(1,k-1):
    for b in range(a+1,k):
        for c in range(b+1,k+1):
            ans+=6*gcd(a,gcd(b,c))
print(ans)

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):
        num = math.gcd(i, j)
        for j in range(1, K+1):
            ans+=math.gcd(num, j)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Apr 12 20:58:46 2020

@author: Kanaru Sato
"""

import math

k = int(input())

sum1 = 0
for i in range(1,k+1):
    sum1 += i

sum2 = 0
for i in range(1,k):
    for j in range(i+1,k+1):
        sum2 += math.gcd(i,j)
sum2 = 6*sum2

sum3 = 0
for i in range(1,k-1):
    for j in range(i+1,k):
        for k in range(j+1,k+1):
            sum3 += math.gcd(math.gcd(i,j),k)
sum3 = 6*sum3

ans = sum1 + sum2 + sum3

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from functools import reduce


def input():
    return sys.stdin.readline().strip()


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


def main():
    K = int(input())
    diff = 0
    diff1 = 0
    same = 0

    for a in range(1, K + 1):
        for b in range(a + 1, K + 1):
            for c in range(b + 1, K + 1):
                diff += gcd_list([a, b, c])

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

    for a in range(1, K + 1):
        same += a

    print(diff * 6 + diff1 * 6 + same)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
k = int(input()) # 入力が1つ
# map(int, input().split()) # 入力が複数
# [int(i) for i in input().split()] # 配列で数字
def gcd(x, y): #GCD
    # greatest_common_divisor
    if x < y:
        x, y = y, x
    if y == 0:
        return 0
    if x % y == 0:
        return y
    return gcd(y, x % y)

temp = []
for i in range(1, k + 1):
    for j in range(1, k + 1):
        temp.append(gcd(i, j))
from collections import Counter
c = Counter(temp)
ans = 0
for t, v in c.items():
    for n in range(1, k + 1):
        ans += gcd(t, n) * v
print(ans)

Submission status: Accepted

Solution code:
import queue
import math
import copy
"""
N = int(input())
#S = input()
# (N,M) = (int(i) for i in input().split(" "))
# A = [int(i) for i in input().split()]
A = []
for i in range(N):
	A.append(int(input()))

print(A)

"""
def T(a,b):
	s = a*b
	if a > b:
		b += a
		a = b - a
		b -= a
	while b % a != 0:
		b %= a
		b += a
		a = b - a
		b -= a
	return a

mp = {}

Ans = 0
K = int(input())
for a in range(1,K+1):
	for b in range(1,K+1):
		t = T(a, b)
		if not t in mp:
			one = 0
			for c in range(1,K+1):
				# print(a,b,c,T(t,c))
				one += T(t,c)
			mp[t] = one
		Ans += mp[t]
print(Ans)

Submission status: Accepted

Solution code:
from functools import reduce
import itertools
import math

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

k = int(input())

sum = 0
# forループのネスト
for a, b, c in itertools.product(range(1, k+1), range(1, k+1), range(1, k+1)):

    sum += gcd(a, b, c)

print(sum)