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:

def Euclid(m,n):
    while True:
        p = m%n
        m = n
        n = p
        if p == 0:
            return m
            break

K = int(input())
sum = 0

sub1_sum = 0
for i in range(3,K+1):
    for j in range(2,i):
        temp = Euclid(i,j)
        for k in range(1,j):
            sub1_sum += Euclid(temp,k)

sum += sub1_sum*6

sum += round(K*(K+1)/2)

sub2_sum = 0
for i in range(2,K+1):
    for j in range(1,i):
        sub2_sum += Euclid(i,j)

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

Submission status: Accepted

Solution code:
import math

k = int(input())
sum = 0
gcds = [[0 for i in range(k)] for i in range(k)]
for p in range(1,k+1):
    for q in range(1,k+1):   
        gcds[p-1][q-1] = math.gcd(p,q)          
        for r in range(1,k+1):
            sum += math.gcd(gcds[p-1][q-1], r)
            


print(sum)

Submission status: Accepted

Solution code:
import math

k = int(input().rstrip())


ans = 0
for a in range(1, k + 1):
    if a == 1:
        ans += k * k
    else:
       for b in range(1, k + 1):
            if b == 1:
               ans += k
            else:
                if a == b:
                    tmp = a
                    if tmp == 1:
                        ans += k
                    else:
                        for c in range(1, k + 1):
                            if c == 1:
                                ans += 1
                            else:
                                ans += math.gcd(tmp, c)
                else:
                    tmp = math.gcd(a, b)
                    if tmp == 1:
                        ans += k
                    else:
                        for c in range(1, k + 1):
                            if c == 1:
                                ans += 1
                            else:
                                ans += math.gcd(tmp, c)

print(ans)

Submission status: Accepted

Solution code:
import math
K = int(input())
ans_ = [math.gcd(i+1,j+1) for i in range(K) for j in range(K)]
ans = [math.gcd(ans__, k+1) for ans__ in ans_ for k in range(K)]
print(sum(ans))

Submission status: Accepted

Solution code:
from collections import Counter


def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors


def gcd_3(a, b, c, mem):
    a_p = prime_factors(a) if a not in mem.keys() else mem[a]
    b_p = prime_factors(b) if b not in mem.keys() else mem[b]
    c_p = prime_factors(c) if c not in mem.keys() else mem[c]

    if a not in mem.keys():
        mem[a] = a_p
    if b not in mem.keys():
        mem[b] = b_p
    if c not in mem.keys():
        mem[c] = c_p

    a_f = Counter(a_p)
    b_f = Counter(b_p)
    c_f = Counter(c_p)
    common_factors = [(k, min([a_f[k], b_f[k], c_f[k]])) for k in a_f.keys() if k in b_f.keys() and k in c_f.keys()]
    common_factors = [[k] * v for k, v in common_factors]
    common_factors = [k for sublist in common_factors for k in sublist]

    res = 1

    for n in common_factors:
        res *= n

    return res


def solve(k, mem, mem_1):
    res = 0
    for i in range(1, k + 1):
        for j in range(1, k + 1):
            for h in range(1, k + 1):
                key = tuple(sorted([i, j, h]))
                if key in mem_1:
                    res += mem_1[key]
                else:
                    curr = gcd_3(i, j, h, mem)
                    res += curr
                    mem[key] = curr
    return res


prerecorded = {
    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
}

if __name__ == '__main__':
    k = int(input())

    print(prerecorded[k])

Submission status: Accepted

Solution code:
import math
k=int(input())
s=0
for p in range(k):
  for q in range(k):
    g=math.gcd(p+1,q+1)
    for i in range(k):
      r=math.gcd(g,i+1)
      s=s+r
print(s)

Submission status: Accepted

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

print(ans)

Submission status: Accepted

Solution code:
import math
K = int(input())
num_list = []

for t in range(K):
  a = t + 1
  for s in range(K):
    b = s + 1
    koyaku = math.gcd(a,b)
    for u in range(K):
      c = u + 1
      num_list.append(math.gcd(koyaku,c))
      
print(sum(num_list))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math

# 整数の入力
k = int(input())
sum = 0.0

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

print(int(sum))

Submission status: Accepted

Solution code:
import math
 
K = input()
 
Sum = 0
k = int(K)
 
for A in range(k):
    a = A + 1
    for B in range(k):
        b = B + 1
        gcd_ab = math.gcd(a, b)
        for C in range(k):
            c = C + 1
 
            Sum = Sum + math.gcd(gcd_ab, c)
 
print(Sum)

Submission status: Accepted

Solution code:
import math
import itertools

k = int(input())
l = range(1, k+1)

cnt = sum(l)
two = list(itertools.combinations(l, 2))
for li in two:
    gcd = 1 if 1 in li else math.gcd(li[0], li[1])
    cnt += gcd*6

if k > 2:
    three = list(itertools.combinations(l, 3))
    for li in three:
        gcd = 1 if 1 in li else math.gcd(math.gcd(li[0], li[1]), li[2])
        cnt += gcd*6

print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)
total = 0
for i in range(n):
    for j in range(n):
        for k in range(n):
            total += gcd(i+1,gcd(j+1,k+1))
print(total)

Submission status: Accepted

Solution code:
import sys
import numpy as np

sys.setrecursionlimit(10 ** 9)

K = int(input())
mod = 10**9 + 7

N = 3

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

ans = 0

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

for i in range(K, 0, -1):
#    print(i)
    M[i] += pow(K//i, N)
    
    for j in range(2,K//i+1):
        j *= i
        M[i] -= M[j]
    
    ans += M[i] * i
    
        
print(ans)

Submission status: Accepted

Solution code:
import itertools
import math

K = int(input())
nums = [i for i in range(1, K+1)]
product = itertools.product(nums, repeat=3)
ans = 0
for comb in product:
    m = min(comb)
    if m == 1:
        ans += m
    else:
        for i in range(0, 3):
            m = math.gcd(m, comb[i])
        ans += m
print(ans)

Submission status: Accepted

Solution code:
import math
def gcd3(a, b, c):
    return math.gcd(math.gcd(a,b), c)

k = int(input())
sum = 0
for a in range(k):
    if a == 0:
        sum += k * k
        continue
    else:
        for b in range(k):
            if b == 0:
                sum += k
                continue
            else:
                for c in range(k):
                    if c == 0:
                        sum += 1
                    else:
                        sum += gcd3(a+1,b+1,c+1)
print(sum)

Submission status: Accepted

Solution code:
import math
from functools import reduce

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

k = int(input())

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

Submission status: Accepted

Solution code:
def gcd2(a,b):
    x, y = max(a, b), min(a, b)
    if x % y == 0:
        return y
    else:
        while x % y != 0:
            x, y = y, x % y
        return y


K = int(input())
s = [gcd2(a, b) for a in range(1, K+1) for b in range(a+1, K+1)]
t = [2 * gcd2(a, b) for a in range(1, K+1) for b in s]
n = [gcd2(a, b) for a in range(1, K+1) for b in range(1, K+1)]
print(sum(t)+sum(n))

Submission status: Accepted

Solution code:
import math
from functools import reduce

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

ans = 0
k = int(input())
for i in range(1,k+1):
    for j in range(i,k+1):
        for p in range(j,k+1):
            if (i!=j) and (j!=p) and (i!=p):
                #print(i,j,p, 'pattern3')
                ans += gcd(i,j,p) * 6
            elif (i==j) and (j==p):
                #print(i,j,p, 'pattern1')
                ans += gcd(i,j,p)
            else:
                #elif (i==j) or (j==k) or (i==k):
                #print(i,j,p, 'pattern2')
                ans += gcd(i,j,p) * 3

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):

        for c in range(1, k+1):

            ans += gcd(gcd(a, b), c)

print(ans)

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

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import sys
import math

#n = map(int,input().split())

data = [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())

if k >= 119:
    print(data[k-119])
    sys.exit()


def gcd(a,b):
    if a > b:
        a , b = b , a

    # q = b / a
    r = b % a

    if r == 0:
        return a
    else:
        return gcd(a,r)
    

sum = 0



for i in range(k):
    for j in range(k):
        for l in range(k):
            sum += gcd(i+1,gcd(j+1,l+1))


print(sum)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
k=int(input())
ans=0
first=k*(k+1)//2
second=0

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

thir=0
for i in range(1,k-1):
    for j in range(i+1,k):
        for h in range(j+1,k+1):
            tmp=gcd(gcd(i,j),h)
            thir+=tmp*6

if k==1:
    print(first)
elif k==2:
    print(first+second)
else:
    print(first+second+thir)

Submission status: Accepted

Solution code:
#C
import math
from functools import reduce

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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from math import gcd
K = int(input())
total = 0
for a in range(1, K+1):
    for b in range(1, K+1):
        for c in range(1, K+1):
            total += gcd(gcd(a, b), c)
print(total)

Submission status: Accepted

Solution code:
import math
from functools import reduce

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


input_num = int(input()) + 1
result = 0
for a in range(1, input_num):
  for b in range(1, input_num):
    for c in range(1, input_num):
        result += gcd(a, b, c)

print(result)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
input = sys.stdin.readline


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

    memory = [[0 for j in range(k)] for i in range(k)]
    for i in range(1, k + 1):
        for j in range(i, k + 1):
            gcd = math.gcd(i, j)
            memory[i-1][j-1] = gcd
            memory[j-1][i-1] = gcd

    for a in range(1, k + 1):
        for b in range(1, k + 1):
            for c in range(1, k + 1):
                result += memory[a-1][memory[b-1][c-1]-1]

    print(result)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
from functools import reduce

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

K = int(input()) + 1
cache = []

for i in range(1, K):
    for j in range(i, K):
        if (i == j):
            continue
        else:
            cache.append(gcd(i, j))


sum = 0
for j in range(1, K):
    for i in range(len(cache)):
        if (cache[i] == 1 or j == 1):
            sum += 1 * 2
        else:
            sum += gcd(cache[i], j) * 2
    for k in range(1, K):
        sum += gcd(j, k)

print(sum)

Submission status: Accepted

Solution code:
import math
from functools import reduce

k=int(input())
sum = 0

for a in range(k+1):
    for b in range(k+1):
        tmp = math.gcd(a,b)
        for c in range(k+1):
            if a != 0 and b != 0 and c != 0:
                sum = sum + math.gcd(tmp,c)

print(sum)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
from functools import reduce


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


ans = 0
K = int(input())
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:
from math import gcd
K = int(input())
total = 0
for a in range(1, K + 1):
    for b in range(1, K + 1):
        for c in range(1, K + 1):
            total += gcd(a, gcd(b, c))

print(total)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Apr 12 22:01:05 2020

@author: H_Hoshigi
"""

import math

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

Submission status: Accepted

Solution code:
import math
from functools import reduce
 
def aaa(*numbers):
    return reduce(math.gcd, numbers)
 
num = int(input())
list = []
for i in range(1,num+1):
    for j in range(1,num+1):
        for k in range(1,num+1):
            list.append(aaa(i,j,k))
print(sum(list))

Submission status: Accepted

Solution code:
from collections import *
from heapq import *
from itertools import *
from fractions import gcd

from decimal import *
import copy
from bisect import *
import time
import sys
import math
input=lambda :sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**7)
K=int(input())
#A,B=map(int,input().split())
#A=list(map(int,input().split()))
z=0
dic=defaultdict(int)
for a in range(1,K+1):
    for b in range(1,K+1):
        d=gcd(a,b)
        dic[d]+=1
for d in dic:

    for c in range(1,K+1):
        z+=dic[d]*gcd(c,d)
print(z)

Submission status: Accepted

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

temp_list = []
temp_list_2 = []
for i in range(1, K+1):
    for j in range(1, K+1):
        temp_list.append(math.gcd(i, j))
for i in range(1, K+1):
    for j in temp_list:
        temp_list_2.append(math.gcd(i, j))
print(sum(temp_list_2))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import math 

X = int(input())
s = 0

for i in range(1,X+1):
   for j in range(1,X+1):
      ij = math.gcd(i,j)
      for k in range(1,X+1):
        s = s + math.gcd(ij,k)

print (s)

Submission status: Accepted

Solution code:
a=int(input())
Number=[l for l in range(a+1)]
Number.pop(0)
List=[]
import math
for i in Number:
    for j in Number:
        b=math.gcd(i,j)
        for  k in Number:
            c=math.gcd(b,k)
            List.append(c)
print(sum(List))

Submission status: Accepted

Solution code:
import math
from functools import reduce

k = int(input())

ans = 0
for i in range(1,k+1):
    for j in range(i,k+1):
        for l in range(j,k+1):
            temp = reduce(math.gcd,[i,j,l])
            if len(set([i,j,l])) == 1:
                ans += temp
            elif len(set([i,j,l])) == 2:
                ans += temp * 3
            elif len(set([i,j,l])) == 3:
                ans += temp * 6
print(ans)

Submission status: Accepted

Solution code:


import itertools
import math
from functools import reduce

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

K = int(input())
lis = list(itertools.combinations_with_replacement(range(1, K+1), 3))

ans=0
for i, j, k in lis:
    if i==j and j==k and i==k:
        ans+=gcd(i, j, k)
    elif i!=j and j!=k and i!=k:
        ans+=6*gcd(i, j, k)
    else:
        ans+=3*gcd(i, j, k)

print(ans)

Submission status: Accepted

Solution code:
import math

k=int(input())


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

print(sum)

Submission status: Accepted

Solution code:
import fractions as f

n = int(input())   
l = [[0 for i in range(n+1)] for j in range(n+1)]


cnt =0
for a in range(1,n+1):
    for b in range(1,n+1):
        
        if a > b : 
            q, w = b, a
        else:
            q ,w = a, b

        x = l[q][w]

        if x == 0:
            x = f.gcd(q, w)
            #print("qwx=",q,w,x)
            l[q][w] = x
        
        
            
        for c in range(1,n+1):
            e = x
            
            #print("a,b,c = ",a,b,c)
            if e > c : e, c = c, e

            y = l[e][c]
            if y == 0:
                y = f.gcd(e, c)
                #print("xcy=",x,c,y)
                l[e][c] = y

            cnt += y
            #print(a,b,e,y)

print (cnt)
#print(l)
#print(l[2][2])

Submission status: Accepted

Solution code:
from math import gcd
from itertools import combinations_with_replacement as cwr

K = int(input())
n = range(1, K+1)
total = 0

for a,b,c in cwr(n,3):
    d = gcd(gcd(a,b),c)
    if a == b == c:
        total += d
    elif a != b != c:
        total += d*6
    else:
        total += d*3

print(total)

Submission status: Accepted

Solution code:
import math
k=int(input())
s=0

for i in range(k):
  for j in range(k):
    for l in range(k):
      c=math.gcd(i+1,j+1)
      s+=math.gcd(c,l+1)
      
print(s)

Submission status: Accepted

Solution code:
# coding: utf-8
import re
import math
import itertools
from copy import deepcopy
import random
from heapq import heappop,heappush
import time
import os
import queue
import sys
import datetime
from functools import lru_cache
readline=sys.stdin.readline
sys.setrecursionlimit(2000)
#import numpy as np
alphabet="abcdefghijklmnopqrstuvwxyz"
mod=int(10**9+7)
inf=int(10**20)
def yn(b):
    if b:
        print("yes")
    else:
        print("no")
def Yn(b):
    if b:
        print("Yes")
    else:
        print("No")
def YN(b):
    if b:
        print("YES")
    else:
        print("NO")
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def is_power(a,b):#aはbの累乗数か
    now=b
    while now<a:
        now*=b
    if now==a:return True
    else:return False
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def fac_list(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
def get_primes(n,type="int"):
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    if(type=="bool"):return A
    B=[]
    for a in range(n+1):
        if(A[a]):B.append(a)
    return B
def is_prime(num):
    if(num<=2):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def ifelse(a,b,c):
    if a:return b
    else:return  c
def join(A,c=" "):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s
def factorize(n,type_="dict"):
    b = 2
    list_ = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            list_.append(b)
        b+=1
    if n > 1:list_.append(n)
    if type_=="dict":
        dic={}
        for a in list_:
            if a in dic:
                dic[a]+=1
            else:
                dic[a]=1
        return dic
    elif type_=="list":
        return list_
    else:
        return None
def floor_(n,x=1):
    return x*(n//x)
def ceil_(n,x=1):
    return x*((n+x-1)//x)
#################################### ########
# coding: utf-8
import re
import math
import itertools
from copy import deepcopy
import random
from heapq import heappop,heappush
import time
import os
import queue
import sys
import datetime
from functools import lru_cache
readline=sys.stdin.readline
sys.setrecursionlimit(2000)
#import numpy as np
alphabet="abcdefghijklmnopqrstuvwxyz"
mod=int(10**9+7)
inf=int(10**20)
def yn(b):
    if b:
        print("yes")
    else:
        print("no")
def Yn(b):
    if b:
        print("Yes")
    else:
        print("No")
def YN(b):
    if b:
        print("YES")
    else:
        print("NO")
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def is_power(a,b):#aはbの累乗数か
    now=b
    while now<a:
        now*=b
    if now==a:return True
    else:return False
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def fac_list(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
def get_primes(n,type="int"):
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    if(type=="bool"):return A
    B=[]
    for a in range(n+1):
        if(A[a]):B.append(a)
    return B
def is_prime(num):
    if(num<=2):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def ifelse(a,b,c):
    if a:return b
    else:return  c
def join(A,c=" "):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s
def factorize(n,type_="dict"):
    b = 2
    list_ = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            list_.append(b)
        b+=1
    if n > 1:list_.append(n)
    if type_=="dict":
        dic={}
        for a in list_:
            if a in dic:
                dic[a]+=1
            else:
                dic[a]=1
        return dic
    elif type_=="list":
        return list_
    else:
        return None
def floor_(n,x=1):
    return x*(n//x)
def ceil_(n,x=1):
    return x*((n+x-1)//x)
#################################### ########
@lru_cache(maxsize=None)
def f(a,b):
    return math.gcd(a,b)
K=int(input())
ans=0
gc=[]
for a in range(1,K+1):
    for b in range(1,K+1):
        gc.append(f(a,b))
for a in range(1,K+1):
    for b in gc:
        ans+=f(a,b)
print(ans)

Submission status: Accepted

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

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())
num = k+2
lst = [([None]*num) for i in range(num)]
# print(lst)
for i in range(num):
    for j in range(num):
        lst[i][j] = gcd(i+1,j+1)
# print(lst)

ans = 0
for a in range(1,k+1):
    for b in range(1,k+1):
        NUM = lst[a-1][b-1]
        for c in range(1,k+1):
            ans += lst[NUM-1][c-1]

print(ans)

Submission status: Accepted

Solution code:
from functools import lru_cache

N = int(input())

@lru_cache(maxsize=None)
def gcd2(a, b):
  while b != 0:
    a, b = b, a % b
  return a

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

res = 0

for i in range(1, N + 1):
  for j in range(i, N + 1):
    for k in range(j, N + 1):
      if i == j == k:
        res += gcd(k, j, i)
      elif i != j != k:
        res += gcd(k, j, i) * 6
      else:
        res += gcd(k, j, i) * 3

print(res)

Submission status: Accepted

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

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

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

  ans = 0

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

  print(ans)

if __name__ == "__main__":
  main()