Problem:


Score : 300 points

Problem Statement

Find \displaystyle{\sum_{a=1}^{K}\sum_{b=1}^{K}\sum_{c=1}^{K} \gcd(a,b,c)}.

Here \gcd(a,b,c) denotes the greatest common divisor of a, b, and c.

Constraints

1 \leq K \leq 200

K is an integer.

Input

Input is given from Standard Input in the following format:

K

Output

Print the value of \displaystyle{\sum_{a=1}^{K}\sum_{b=1}^{K}\sum_{c=1}^{K} \gcd(a,b,c)}.

Sample Input 1

2

Sample Output 1

9

\gcd(1,1,1)+\gcd(1,1,2)+\gcd(1,2,1)+\gcd(1,2,2)
+\gcd(2,1,1)+\gcd(2,1,2)+\gcd(2,2,1)+\gcd(2,2,2)
=1+1+1+1+1+1+1+2=9

Thus, the answer is 9.

Sample Input 2

200

Sample Output 2

10813692



Sample input:
2


Sample output:
9

Submission status: Accepted

Solution code:
import math
K=int(input())
ans=0
for a in range(1,K+1):
    for b in range(a,K+1):
        for c in range(b,K+1):
            tempgcd=math.gcd(a,b)
            if a==b or b==c or a==c:
              if a==b and b==c:
                ans=ans+math.gcd(tempgcd,c)
              else:
                ans=ans+3*math.gcd(tempgcd,c)
            else:
              ans=ans+6*math.gcd(tempgcd,c)
            
print(ans)

Submission status: Accepted

Solution code:
import math
from functools import reduce


K = int(input())


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

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

print(sum)

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

Submission status: Accepted

Solution code:
mod = 10**9 + 7
mod2 = 2**61 + 1
int1 = lambda x: int(x) - 1
from collections import deque
import heapq
import time
from bisect import bisect_left, insort_left, bisect_right
import sys
import random
import itertools


# input = sys.stdin.readline
def input():
    return sys.stdin.readline().strip("\n").strip(" ")


_NUMINT_ALL = list(range(10))
_START_TIME = time.time()
INDEX_KETA = 10**12
INF = 9223372036854775807  # 符号つきlong longの最大値。10の18乗より大きく、10の19乗より小さい

def main():
    ans = solve()

    if ans is True or ans is False:
        YesNo(ans)
    elif ans is None:
        return

    if isinstance(ans, tuple):
        split_print_space(ans)
    else:
        print(ans)


def solve():
    K = iip()
    ans = 0

    t = time.time()

    memo = {}
    for i in range(1, K+1):
        for j in range(1, K+1):
            k1 = saidai_kouyakusuu2(i, j)
            for k in range(1, K+1):
                d = saidai_kouyakusuu2(k1, k)
                ans += d

    #print(time.time() - t)

    print(ans)

def saidai_kouyakusuu2(a, b):  # 最大公約数
    a, b = sorted([a, b])
    while True:
        if a == b:
            return a
        if b > a:
            if b % a == 0:
                return a
            else:
                b %= a

        if a > b:
            if a % b == 0:
                return b
            else:
                a %= b


#####################################################ライブラリ集ここから


def kiriage_warizan(a, b):
    return -(-a // b)


def iip(listed=False):  # 数字のinputをlistで受け取る
    d = input().rstrip("\n").split()
    try:
        ret = [int(i) for i in d]
    except:
        ret = [int(i) if i in _NUMINT_ALL else i for i in d]
        if len(ret) == 1 and listed is False:
            return ret[0]

    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def iipt(l, listed=True):  # 縦向きに並んでいるデータをリストに落とし込む(iip利用)
    if isinstance(l, list):
        l = l[0]  # 間違って要素１個のタプルを渡されても受け取る
    assert isinstance(l, int)
    ret = []
    for i in range(l):
        ret.append(iip(listed=listed))
    return ret


def saidai_kouyakusuu(A):  # 最大公約数
    l = len(A)
    while True:
        m = min(A)
        mx = max(A)
        if m == mx:
            return m

        for i in range(l):
            if A[i] % m == 0:
                A[i] = m
            else:
                A[i] %= m


def flatten(l):
    return list(itertools.chain.from_iterable(l))


def index_sorted(sorted_list, target):
    idx = bisect_left(sorted_list, target)
    if idx != len(sorted_list) and sorted_list[idx] == target:
        return idx
    else:
        return False


def time_debug_10percent():
    a = random.randint(0, 9)
    if a == 9:
        sys.exit()


def time_debug(t):
    time.sleep(_START_TIME + t - time.time())
    sys.exit()


def make_graph_edge_flat(N):  # グラフ作成のための辺をリストで返す
    ret = []
    for i in range(N - 1):
        a, b, c = iip()
        a -= 1
        b -= 1
        ret[a].append((b, c))
        ret[b].append((a, c))
    return ret


def sort_tuples(l, index):  # タプルのリストを特定のインデックスでソートする
    if isinstance(l, list):
        l.sort(key=lambda x:x[index])
        return l
    else:
        l = list(l)
        return sorted(l, key=lambda x:x[index])


def count_elements(l):  # リストの中身の個数を種類分けして辞書で返す
    d = {}
    for i in l:
        if i in d:
            d[i] += 1
        else:
            d[i] = 1
    return d


def safeget(l, index, default="exception"):  # listの中身を取り出す時、listからはみ出たり
    if index >= len(l):  # マイナスインデックスになったりするのを防ぐ
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。配列の長さは", len(l), "です"]))
        else:
            return default
    elif index < 0:
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。負の値は許可されていません"]))
        else:
            return default
    else:
        return l[index]


def sortstr(s):  # 文字列をソートする
    return "".join(sorted(s))


def iip_ord(startcode="a"):  # 文字列を数字の列に変換する(数字と文字は1:1対応)
    if isinstance(startcode, str):
        startcode = ord(startcode)
    return [ord(i) - startcode for i in input()]


def YesNo(s):  # TrueFalseや1, 0をYesNoに変換する
    if s:
        print("Yes")
    else:
        print("No")


def fprint(s):  # リストを平たくしてprintする(二次元リストを見やすくしたりとか)
    if isinstance(s, int):
        print(s)
        return
    keta = max([len(str(i)) for i in itertools.chain.from_iterable(s)])
    print("--------")
    for i in s:
        print([str(j).rjust(keta) for j in i])
    print("--------")


def bitall(N):  # ビット全探索用のインデックスを出力
    ret = []
    for i in range(2**N):
        a = []
        for j in range(N):
            a.append(i % 2)
            i //= 2
        ret.append(a)
    return ret


def split_print_space(s):  # リストの中身をスペース区切りで出力する
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):  # リストの中身を改行区切りで出力する
    print("\n".join([str(i) for i in s]))


def soinsuu_bunkai(n):  # 素因数分解
    ret = []
    for i in range(2, int(n**0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):  # nCrをmodを使って計算する
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):  # modnにおける逆元を計算
    return power(n, mod - 2)


def power(n, p, mod_=mod):  # 繰り返し二乗法でn**p % modを計算
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_)**2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


def nibutan_func(func, target, left, right, side="left", seido=1):  # 関数を二分探索
    l = left
    r = right
    if seido == 1:
        x = (l + r) // 2
    else:
        x = (l + r) / 2
    while r - l > seido:
        # print(x)
        if seido == 1:
            x = (l + r) // 2
        else:
            x = (l + r) / 2
        if func(x) == target:
            if side == "left":
                r = x
            else:
                l = x


        elif func(x) > target:
            r = x
        else:
            # print(r, l)
            l = x

    # print(l, r)
    if side == "left" and func(r) == target:
        return r
    elif side != "left" and func(l) == target:
        return l
    elif side == "left":
        return l
    else:
        return r


def nibutan_list(list_, target, side="left"):  # リストを二分探索
    if not isinstance(list_, list):
        list_ = list(list_)

    l = 0
    r = len(list_)
    x = (l + r) // 2
    while r - l > 1:
        x = (l + r) // 2
        if list_[x] == target:
            return x
        elif list_[x] > target:
            r = x
        else:
            l = x

    if side == "left" or list_[x] == target:
        return l
    else:
        return r


class UfTree():
    def __init__(self, maxnum):
        self.parent = list(range(maxnum))
        self._size = [1] * maxnum
        self.rank = [0] * maxnum

    def size(self, a):
        return self._size[self.root(a)]

    def root(self, a):
        rank = 0
        cur = a
        while True:
            if self.parent[cur] == cur:
                # for i in path: # 経路圧縮
                #    self.parent[i] = cur
                return cur
            else:
                self.parent[cur] = self.parent[self.parent[cur]]
                cur = self.parent[cur]
                rank += 1

    def unite(self, a, b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb:
            return self

        self._size[ra] += self._size[rb]
        self.parent[rb] = ra
        return self


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from math import gcd

n = int(input())

ans = 0
for i in range(1, n+1):
    for j in range(1, n+1):
        for k in range(1, n+1):
            if i == j and j == k:
                ans += i
            elif i == 1 or j == 1 or k == 1:
                ans += 1
            else:
                ans += gcd(gcd(i , j), k)

print(ans)

Submission status: Accepted

Solution code:
import math
from functools import reduce

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

K = int(input())

gcd_sum = 0

for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            gcd_sum += gcd(a,b,c)

print(gcd_sum)

Submission status: Accepted

Solution code:
import math


k = int(input())
ans = 0
dic = {}
for a in range(1, k+1):
    for b in range(1, k+1):
        tmp = math.gcd(a,b)
        for c in range(1,k+1):
            ans += math.gcd(tmp, c)
print(ans)

Submission status: Accepted

Solution code:
import collections

def gcd(a,b):
    if a < b:
        a, b = b, a
    q = a // b
    r = a - q * b
    if r == 0:
        return b
    else:
        return gcd(b,r)

K = int(input())

a = []

for i in range(1,K+1):
    for j in range(1, K+1):
        a.append(gcd(i,j))
        
col = collections.Counter(a)

sum = 0
for k in range(1, K+1):
    for key, value in col.items():
         sum += gcd(k, key) * value
print(sum)

Submission status: Accepted

Solution code:
import math

N = int(input())
g=0
for a in range(N):
    for b in range(N):
        g_1=math.gcd((a+1),(b+1))
        for c in range(N):
            g = g + math.gcd(g_1,(c+1))
print(g)

Submission status: Accepted

Solution code:
from math import gcd

k = int(input())

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

print(s)

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:
from functools import reduce

k = int(input())


def gcd(a, b):
    # 最大公約数
    while b:
        a, b = b, a % b
    return a


def gcds(*nums):
	return reduce(gcd, nums)


res1 = 0
for a in range(1, k + 1):
	for b in range(a + 1, k + 1):
		for c in range(b + 1, k + 1):
			res1 += gcds(a, b, c) * 6

res2 = 0
for a in range(1, k + 1):
	for b in range(a + 1, k + 1):
		res2 += gcd(a, b) * 2

res3 = k * (k + 1) // 2

print(res1 + res2 * 3 + res3)

Submission status: Accepted

Solution code:
from fractions import gcd
K = int(input())
ans = 0
dp = [0]*201

for i in range(1,K+1):
    for j in range(1,K+1):
        S = 0
        n = gcd(i,j)
        if dp[n] != 0:
            ans += dp[n]
        else:
            for k in range(1,K+1):
                S += gcd(k,n)
            ans += S
            dp[n] = S

print(ans)

Submission status: Accepted

Solution code:
import math
K = int(input())
ans = 0
result = 0
dp = [[[0 for i in range(K+1)] for i in range(K+1)]for i in range(K+1)]
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            if dp[i][j][k] == 0:
                x = math.gcd(i,j)
                y = math.gcd(j,k)
                ans = math.gcd(x,y)
                dp[i][j][k] = ans
                dp[j][i][k] = ans
                dp[k][i][j] = ans
                dp[k][j][i] = ans
                result += ans
            else:
                result += max(dp[i][j][k],dp[j][i][k],dp[k][i][j],dp[k][j][i])
print(result)

Submission status: Accepted

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


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

Submission status: Accepted

Solution code:
import math
import time
t1 = time.time()
N = int(input())
answer = 0
for i in range(1, N-1):
    for j in range(i+1, N):
        x = math.gcd(i, j)
        for k in range(j+1, N+1):
            answer += 6*math.gcd(x, k)
for i in range(1, N+1):
    for j in range(1, N+1):
        if i != j:
            answer += 3*math.gcd(i, j)
        else:
            answer += math.gcd(i, j)
print(answer)

Submission status: Accepted

Solution code:
import itertools
import math

m = int(input())
g = list(range(1, m+1))
res = 0
for c in itertools.combinations_with_replacement(g, 3):
  set_c = set(c)
  set_list_c = list(set_c)
  if len(set_c) == 3:
    n = 6
    tmp_res = math.gcd(set_list_c[0], set_list_c[1])
    tmp_res = math.gcd(tmp_res, set_list_c[2])
  elif len(set_c) == 2:
    n = 3
    tmp_res = math.gcd(set_list_c[0], set_list_c[1])
  else:
    n = 1
    tmp_res = set_list_c[0]
  res += tmp_res * n
print(res)

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

Submission status: Accepted

Solution code:
import sys
# sys.stdin = open('input.txt')

from math import gcd


k = int(input())
ans = 0
memory = {}

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

print(ans)

Submission status: Accepted

Solution code:
import math

import sys
k = sys.stdin.readline()
k = int(k)
sum = 0
for x in range(1,k+1):
    for y in range(x,k+1):
        for z in range(y,k+1):
            if len(set([x,y,z])) is 1:
                sum = sum +math.gcd(math.gcd(x, y), math.gcd(y, z))
            elif len(set([x,y,z])) is 2:
                sum = sum + 3 * math.gcd(math.gcd(x, y), math.gcd(y, z))
            elif len(set([x,y,z])) is 3:
                sum = sum + 6* math.gcd(math.gcd(x, y), math.gcd(y, z))
print(sum)

Submission status: Accepted

Solution code:
from fractions import gcd

k=int(input())
count = 0

g = {}
for i in range(1,k+1):
    for j in range(i,k+1):
        x = gcd(i,j)
        if i==j:
            y=1
        else:
            y=2
        if x in g:
            g[x] += y
        else:
            g[x] = y
            
for i in g:
    for j in range(1,k+1):
        x = gcd(i,j)
        count += x*g[i]
        
print(count)

Submission status: Accepted

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

def gcd(a, b): 
    dividend = max(a, b)
    divider = min(a, b)

    if divider == 0:
        return dividend
    while dividend % divider != 0:
        r = dividend % divider
        dividend = divider
        divider = r 

    return divider

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

Submission status: Accepted

Solution code:
import math
from functools import lru_cache

@lru_cache(maxsize=10**6)
def cached_gcd(i, j):
    return math.gcd(i, j)

if __name__ == '__main__':
    N = int(input())
    total = 0
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            g = cached_gcd(j, i)
            for k in range(1, N + 1):
                total += cached_gcd(k, g)
    print(total)

Submission status: Accepted

Solution code:
from itertools import combinations_with_replacement
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    ans=0
    K=int(input())
    KK=[i for i in range(1,K+1)]
    from functools import reduce
    from math import gcd

    I=list(combinations_with_replacement(KK,3))
    for i in I:
        ls=len(set(i))
        if ls==1:
            ans+=reduce(gcd,i)
        elif ls == 2:
            ans+=reduce(gcd,i)*3
        else:
            ans+=reduce(gcd,i)*6





    print(ans)


resolve()

Submission status: Accepted

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

def gcds(a, b, c):
  tmp = gcd(a, b)
  return gcd(tmp, c)

def comb(i, j, k):
  l = [i, j, k]
  s = set(l)
  if len(s)==1:
    return 1
  elif len(s)==2:
    return 3
  else:
    return 6

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):
      ans += comb(i, j, k) * gcds(i, j, k)
      
print(ans)

Submission status: Accepted

Solution code:
import math
from functools import reduce

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

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

Submission status: Accepted

Solution code:
K = int(input())

import math
 
gcd_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):
            gcd_sum += math.gcd(ab,c)       
 
print(gcd_sum)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(4100000)


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


k=int(input())
ans=0
for i in range(1,k+1):
  for j in range(1,k+1):
    d=gcd(i,j)
    for l in range(1,k+1):
      if d!=1:
        ans+=gcd(d,l)
      else:
        ans+=1


print(ans)

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 l in range(j,k+1):
      if l==i:
        ans+=gcd(i,j,l)
      elif i==j or j==l:
        ans+=3*gcd(i,j,l)
      else:
        ans+=6*gcd(i,j,l)
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(a+1,k):
        for c in range(b+1,k+1):
            ans += math.gcd(math.gcd(a, b), c)*6

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

for a in range(1,k+1):
    ans += a

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math
from functools import reduce

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):
            abc = [a, b, c]
            #print(abc)

            abc_gcd = reduce(math.gcd, abc)
            set_abc = set(abc)
            #print(set_abc)
            # a, b, cが全て同じならこの組み合わせは1回だけ
            if len(set_abc) == 1:
                ans += abc_gcd
            # a, b, cに数字が2つ存在するならこの組み合わせは3回
            elif len(set_abc) == 2:
                ans += (abc_gcd * 3)
            # a, b, cの数字がすべて違えばこの組み合わせは6回
            elif len(set_abc) == 3:
                ans += (abc_gcd * 6)

print(ans)

Submission status: Accepted

Solution code:
k=int(input())
import functools,math
sum = 0

# 3つ同じ場合
for a in range(1,k+1):
    sum += a
# 2つ同じ場合, ABBとする。
for a in range(1,k+1):
    for b in range(1,k+1):
        if a==b:
            continue
        sum += math.gcd(a,b)*3
# すべて異なる場合
for a in range(1,k+1):
    for b in range(a+1,k+1):
        for c in range(b+1,k+1):
            sum += functools.reduce(math.gcd, [a,b,c]) * 6
            #print (a,b,c,functools.reduce(math.gcd, [a,b,c]))
print (sum)

Submission status: Accepted

Solution code:
import math
from functools import reduce

K = int(input())

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

print(sum)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
import itertools
from functools import reduce


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


K = int(input())
GCD = 0
range_list = list(range(1, K+1))
iterator = itertools.product(range_list, range_list, range_list)
for a in range(1, K+1):
    for b in range(a, K+1):
        for c in range(b, K+1):
            val= gcd(a, b, c)
            if a == b and b == c:
                GCD += val
            elif a == b or b == c:
                GCD += 3 * val
            else:
                GCD += 6 * val

print(GCD)

Submission status: Accepted

Solution code:
import math
from functools import reduce

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

sum1 = 0
sum3 = 0
sum6 = 0
for i in range(1, n+1):
  for j in range(1, i+1):
    for k in range(1, j+1):
      if i!=j and j!=k and k!=i:
        sum6 += gcd(i,j,k)
      elif i==j and j==k:
        sum1 += i
      else:
        sum3 += gcd(i,j,k)

sum = sum1 + sum3*3 + sum6*6

print(sum)

Submission status: Accepted

Solution code:
import math

N = int(input())

result = 0

for a in range(1, N+1):
    for b in range(1, N+1):
        if math.gcd(a,b) == 1:
            result += 1*N
        else:
            for c in range(1, N+1):
                result += math.gcd(math.gcd(a,b),c)

print(result)

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

Submission status: Accepted

Solution code:
import math

K=int(input())
num=0
for i in range(1,K+1):
  for j in range(1,K+1):
    gcd_2=math.gcd(i,j)
    for k in range(1,K+1):
      gcd_3=math.gcd(gcd_2,k)
      num=num+gcd_3
print(num)

Submission status: Accepted

Solution code:
def gcd(x, y):
  while y != 0:
    x, y = y, x%y
  return x
 
K = int(input())
Klist = [i+1 for i in range(K)]
total = 0
for a in Klist:
  for b in Klist:
    for c in Klist:
      total += gcd(gcd(a, b), c)
print(total)

Submission status: Accepted

Solution code:
import math
from functools import reduce

def gcd_list(a,b,c):
    return reduce(math.gcd, [a,b,c])

n = int(input())
cnt = 0
for i in range(1,n + 1):
    for j in range(1,n + 1):
        for k in range(1,n + 1):
            
            cnt += gcd_list(i,j,k)
print(cnt)

Submission status: Accepted

Solution code:
# gcdどこにあるかわからんからスクラッチ

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

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

# dd = {}
# for ii in range(1, 200):
#     ans = 0
#     for i in range(1, ii + 1):
#         for j in range(1, ii + 1):
#             for p in range(1, ii + 1):
#                 t = gcd(gcd(i, j), p)
#                 ans += t
#     dd[ii] = ans
#     print(ans)
#     ans = 0

# with open("annsss.txt", "w", encoding="utf-8") as f:
#     for k, v in dd.items():
#         f.write("{}:{},".format(k, v))

# print(ans)

Submission status: Accepted

Solution code:
from functools import reduce
import fractions
import math
k=int(input())
m=0
for i in range(1,k+1):
    for j in range(i,k+1):
        for p in range(j,k+1):
            l=[i,j,p]
            if i==j==p:
                m+=reduce(math.gcd,l)
            elif (i==j and i!=p) or (i==p and i!=j) or (j==p and i!=p):
                m+=3*reduce(math.gcd,l)
            else:
                m+=6*reduce(math.gcd,l)
print(m)

Submission status: Accepted

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

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

K = int(input())
total = 0

# 3 scenarios
# X-X-X
# X-X-Y
# X-Y-Z

for a in range(1, K+1):
    for b in range(1, K+1):
        for c in range(1, K+1):
            total += tgcd(a, b, c)

        
print(total)
#total += sum(range(1, 201))
#print(total + sum(range(1,201)))
#print("diff", 10813692-total)

Submission status: Accepted

Solution code:
from itertools import combinations

def gcd(a, b):
    if a < b:
        tmp = a
        a = b
        b = tmp

    r = a % b
    while r!=0:
        a = b
        b = r
        r = a % b
    return b

def gcd_three(a, b, c):
    temp = gcd(a, b)
    return gcd(temp, c)

K = int(input())
ans = 0

ans += sum(range(1, K+1))
ans += 6*sum([gcd(*t) for t in combinations(range(1, K+1), 2)])
ans += 6*sum([gcd_three(*t) for t in combinations(range(1, K+1), 3)])

print(ans)

Submission status: Accepted

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

def gcd(num_list):
    ans = 0
    for i in num_list:
        ans = gcd_base(ans, i)
    return ans

k = int(input())
ans = 0
for i in range(1, k-1):
    for j in range(i+1, k):
        for l in range(j+1, k+1):
            ans += 6*gcd([i,j,l])
for i in range(1, k):
    for j in range(i+1, k+1):
        ans += 6*gcd_base(i, j)
for i in range(1, k+1):
    ans += i
print(ans)

Submission status: Accepted

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

import math
from functools import reduce

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


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