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


# 8000000をgcd愚直は間に合うか？ #3つの順番は入れ替わってもよい
# 埋め込むか

def f(K):
    nums = list(range(1, K + 1))
    ans = 0
    for a, b, c in product(nums, nums, nums):
        ans += gcd(gcd(a, b), c)
    return ans


print(f(int(input())))

Submission status: Accepted

Solution code:
import itertools
import math
 
K = int(input())
l = range(1, K+1)
ans = sum(l)
 
for a, b in itertools.combinations(l, 2):
    ans += math.gcd(a, b) * 6
 
for a, b, c in itertools.combinations(l, 3):
    ans += math.gcd(math.gcd(a,b), c)*6
    
        
print(ans)

Submission status: Accepted

Solution code:
import math

K = int(input())

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

print(sum)

Submission status: Accepted

Solution code:
import math
def getInput():
    return [int(i) for i in input().rstrip().split(' ')]


N = getInput()[0]
sums = 0
for i in range(1, N+1):
    for j in range(1, N+1):
        n = math.gcd(i, j)
        for k in range(1, N+1):
            sums += math.gcd(n, k)

print(sums)

Submission status: Accepted

Solution code:
from math import gcd

k = int(input())
tot = 0

for l in range(1, k + 1):
    for m in range(1, k + 1):
        for n in range(1, k + 1):
            tot += gcd(gcd(l, m), n)
print(tot)

Submission status: Accepted

Solution code:
import math

l = int(input())
s = 0

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

Submission status: Accepted

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

res = 0
for a in range(K):
    for b in range(K):
        for c in range(K):
            res += math.gcd(math.gcd(a+1, b+1), c+1)
print(res)

Submission status: Accepted

Solution code:
import math
from functools import reduce
  
k = int(input())
k+=1

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

print(sum)

Submission status: Accepted

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

K = int(input())
ans = 0

for i in range(1, K+1):
    for j in range(i, K+1):
        for k in range(j, K+1):
            if i == j and k == i:
                ans += gcd(gcd(i, j), k)
            elif i == j or k == i or j == k:
                ans += 3 * gcd(gcd(i, j), k)
            else:
                ans += 6 * gcd(gcd(i, j), k)

print(ans)

Submission status: Accepted

Solution code:
import math
from functools import reduce
from itertools import *
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 product([i for i in range(1,K+1)], repeat = 3):
  ans += gcd(i[0],i[1],i[2])
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):
        x = math.gcd(i, j)
        for k in range(1, K+1):
            ans += math.gcd(x, k)

print(ans)

Submission status: Accepted

Solution code:
i=int(input())
a=[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]
print(a[i])

Submission status: Accepted

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

s=0

for i in range(1,K+1):
    for j in range(1,K+1):
        a=gcd(i,j)
        for k in range(1,K+1):
            s+=gcd(a,k)

print(s)

Submission status: Accepted

Solution code:
from functools import reduce
import fractions

def main():
    import math
    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 += reduce(lambda a,b: math.gcd(a,b), [i,j,l])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
from functools import reduce
 
def gcd(*numbers):
    return reduce(math.gcd, numbers)
 
K = int(input())
B = list()
a = int()
b = int()
c = int()
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:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
import sys,bisect,string,math,time,functools,random
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[];g=[[] for i in range(n)]
    for i in range(E):
        inp=LI();org_inp.append(inp)
        if index==0:inp[0]-=1;inp[1]-=1
        if len(inp)==2:
            a,b=inp;g[a].append(b)
            if not Directed:g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp;aa=(inp[0],inp[2]);bb=(inp[1],inp[2]);g[a].append(bb)
            if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,boundary=1,search=[],replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,boundary=1,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):return [[tb//(n**bt)%n for bt in range(k)] for tb in range(n**k)]
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)
def show2d(g,h,w):
    for i in range(h):show(g[i*w:i*w+w])

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()

## return prime factors of N as dictionary {prime p:power of p}
## within 2 sec for N = 2*10**20+7
def primeFactor(N):
    i,n=2,N
    ret={}
    d,sq=2,99
    while i<=sq:
        k=0
        while n%i==0:
            n,k,ret[i]=n//i,k+1,k+1
        if k>0 or i==97:
            sq=int(n**(1/2)+0.5)
        if i<4:
            i=i*2-1
        else:
            i,d=i+d,d^6
    if n>1:
        ret[n]=1
    return ret


## return the list of prime numbers in [2,N], using eratosthenes sieve
## within 2sec for N = 1.2*10**7
def PrimeNumSet(N):
    Max = int(N**0.5)
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList:
        if seachList[0] <= Max:
            break
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum

## retrun LCM of numbers in list b
## within 2sec for no of B = 10*5  and  Bi < 10**6
def LCM(b,mo=10**9+7):
    prs=PrimeNumSet(max(b))
    M=dict(zip(prs,[0]*len(prs)))
    for i in b:
        dc=primeFactor(i)
        for j,k in dc.items():
            M[j]=max(M[j],k)
    
    r=1
    for j,k in M.items():
        if k!=0:
            r*=pow(j,k,mo)
            r%=mo
    return r

show_flg=False
show_flg=True


#C
g=[[1]*201 for i in range(201)]
for a in range(1,201):
    for b in range(1,201):
        g[a][b]=math.gcd(a,b)

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

Submission status: Accepted

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

def gcd(a,b):
    return math.gcd(a,b)
cnt=0
for i in range(1,K+1):
    for m in range(1,K+1):
        d = math.gcd(i,m)
        for u in range(1,K+1):
            cnt+=math.gcd(d,u)
            
print(cnt)

Submission status: Accepted

Solution code:
from math import gcd

k = int(input())

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

print(sum)

Submission status: Accepted

Solution code:
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)
    
K = int(input())
cnt = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            cnt += gcd(i,j,k)
            
print(cnt)

Submission status: Accepted

Solution code:
import sys; sys.setrecursionlimit(2147483647); input = sys.stdin.readline
from math import floor, ceil, sqrt, factorial, log
from collections import Counter, defaultdict, deque
from operator import itemgetter
INF = float('inf'); MOD = 10**9+7
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(MI())
def LIR(n): return [LI() for i in range(n)]
def IS(): return input().rstrip()
def gcd_core(a, b):
    if b == 0: return a
    else: return gcd_core(b, a % b)
def gcd(arr):
    g = gcd_core(arr[0], arr[1])
    for i in range(2, len(arr)): g = gcd_core(g, arr[i])
    return g
def main():
    K = I()
    for a in range(1, K+1):
        for b in range(a, K+1):
            for c in range(b, K+1):
                x = len({a, b, c})
                if x == 1: pass
                elif x == 2: x = 3
                else: x = 6
                yield gcd([a, b, c])*x
if __name__ == '__main__':
    print(sum(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 k in range(1,K+1):
            ans += gcd(gcd(i,j),k)
print(ans)

Submission status: Accepted

Solution code:
import sys
#from fractions import gcd
from math import gcd
from itertools import combinations
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

K = int(read())
ans = 0

for a in range(1, K + 1):
    for b in range(1, K + 1):
        acc = gcd(a, b)
        for c in range(1, K + 1):
            acc_ = gcd(acc, c)
            ans += acc_
print(ans)

Submission status: Accepted

Solution code:
K=int(input())

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)
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:
from math import gcd
n=int(input())
s=0
for i in range(1,n+1):
  for j in range(1,n+1):
    for k in range(1,n+1):
      s+=gcd(gcd(i,j),k)
print(s)

Submission status: Accepted

Solution code:
#C - Sum of gcd of Tuples (Easy)
K = int(input())
DP =[]
ans = 0
import math
# from functools import reduce
# def gcd(*numbers):
#     return reduce(math.gcd, numbers)


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

for i in range(1, K + 1):
    for j in range(1, K + 1):
        a = math.gcd(i,j)
        for k in range(1,K+1):
            b = math.gcd(a,k)
            ans += b

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
import sys
import heapq
import bisect
import math
import itertools
import string
import queue
import copy
import time
# import numpy as np
from fractions import gcd

sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10 ** -7

def inp(): return int(sys.stdin.readline())
 
def inp_list(): return list(map(int, sys.stdin.readline().split()))

def lcm(x, y): return (x * y) // gcd(x, y)


def gcd_3(x, y, z):
    return gcd(gcd(x, y), z)

K = inp()

dic = {} # key: (i, j, k), el: gcd(i, j, k)
ans = 0
for i in range(1, K + 1):
    for j in range(i, K + 1):
        tmp = gcd(i, j)
        for k in range(j, K + 1):
            a = gcd(tmp, k)
            if i == j == k:
                ans += a
            elif i == j or j == k:
                ans += a * 3
            else:
                ans += a * 3 * 2
print(ans)

Submission status: Accepted

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

def gcd_xyz(x, y, z):
  xy = gcd(x, y)
  xyz = gcd(xy, z)
  return xyz

def past(p):
  if(p == 2):
    return 1
  else:
    return past(p-1)+(p-2)*4+6

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 += gcd_xyz(i,j,k)
print(sum)

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

print(ans)

Submission status: Accepted

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

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

n = int(input())

total = 0
for i in range(1, n+1):
    for j in range(i, n+1):
        for k in range(j, n+1):
            if  i == j and j == k and i == k:
                x = 1
            elif i != j and j != k and i != k:
                x = 6
            else:
                x = 3
            
            total += x * gcd_list([i, j, k])
        
print(total)

Submission status: Accepted

Solution code:
import math
from functools import reduce


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


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

Submission status: Accepted

Solution code:
k=int(input())
ans=0
import math
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)

def gcdlist(l):
    a = l[0]
    for i in range(len(l)):
        a = gcd(a,l[i])
    return a

sumlis={}
for a in range(1,k+1):
    for b in range(1,k+1):
        t=math.gcd(a,b)
        for c in range(1,k+1):
            ans+=math.gcd(t,c)
                
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from math import gcd
 
def main():
  k = int(input())
  ans = 0
  for a in range(1, k+1):
    for b in range(a, k+1):
      x = gcd(a,b)
      for c in range(b,k+1):
        if a==b and b==c:
          ans += a
        elif a==b or b==c:
          ans += gcd(x,c) * 3
        else:
          ans += gcd(x,c) * 6
  print(ans)
  
  
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import math

K = int(input())
sum = 0
kl = range(1, K+1)

for i in kl:
    for j in kl:
        for k in kl:
            sum += math.gcd(i, math.gcd(j, k))
print(sum)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
N = int(input())
#sum_ = 1+N
sum_ = 0
for i in range(1, 1+N):
    for j in range(1, 1+N):
        a = math.gcd(i, j)
        for k in range(1, 1+N):
            sum_ += math.gcd(a, k)
            
print(sum_)

Submission status: Accepted

Solution code:
from math import gcd

if __name__ == '__main__':
    n = int(input())
    count = 1
    result = 0

    while count <= n:
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                # print(f"gcd({count}, {i}, {j})")
                result += gcd(count, gcd(i, j))
        count += 1

    print(result)

Submission status: Accepted

Solution code:
def divisors(n):
    res = []
    for d in range(1, int(n**0.5)+1):
        if n%d==0:
            res.append(d)
            res.append(n//d)
    res = sorted(set(res))
    return res

# 素因数分解
def prime_decomposition(n):
    i = 2
    table = []
    while i * i <= n:
        while n % i == 0:
            n //= i
            table.append(i)
        i += 1
    if n > 1:
        table.append(n)
    return table

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

K = int(input())
N = 3
invK = modinv(K)
P = [0] * (K+1)
mod = 10**9+7
for i in range(1, K+1):
    p = pow(K//i * invK, N, mod)
    P[i] = p
KN = pow(K, N, mod)
ans = 0


# https://kazuma8128.hatenablog.com/entry/2018/07/29/231819
for i in range(K, 1, -1):
    #print(i, divisors(i))
    for d in divisors(i):
        if d!=i:
            P[d] -= P[i]
for i, p in enumerate(P[1:], 1):
    n = p * KN % mod
    #print(i, n)
    ans = (ans + n * i) % mod
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

k = int(input())
s = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        ab = math.gcd(a, b)
        for c in range(1, k+1):
            s += math.gcd(ab, c)
print(s)

Submission status: Accepted

Solution code:
K = int(input())

import math

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

print(ans)

Submission status: Accepted

Solution code:
import sys, os, math

def get_cd(n):
    cd = []
    for i in range(1, int(n/2)+1):
        if n % i == 0:
            cd.append(i)
        else:
            continue
    cd.append(n)
    return cd

def get_gcd(a, b, c, cd_d):
    if 1 in [a, b, c]:
        return 1
    else:
        cd = sorted(list(set(cd_d[a]) & set(cd_d[b]) & set(cd_d[c])))
        return cd[-1]

if __name__ == '__main__':
    k = int(input())
    cc_d = {}
    for i in range(1, k+1):
        cc_d[i] = get_cd(i)

    computed_d = {}
    s = 0
    for a in range(1, k+1):
        for b in range(a, k+1):
            for c in range(b, k+1):
                if a == b == c:
                    s += a
                else:
                    gcd = get_gcd(a, b, c, cc_d)
                    if a != b != c:
                        s += gcd*6
                    else:
                        s += gcd*3
    print(s)

Submission status: Accepted

Solution code:
def gcd(numbers):
    numbers.sort()
    a = numbers[1]
    b = numbers[0]
    ans = b
    while True:
        q, mod = divmod(a, b)
        if mod == 0:
            break
        a = b
        b = mod
        ans = mod
    return ans

K = int(input())
numbers = []

for i in range(K, 0, -1):
    for j in range(i, 0, -1):
        for k in range(j, 0, -1):
            numbers.append([i, j, k])

gcd_sum = 0
for number in numbers:
    dup = len(set(number))
    a, b, c = number
    if dup == 1:
        gcd_sum += gcd([gcd([a, b]), c])
    elif dup == 2:
        gcd_sum += gcd([gcd([a, b]), c]) * 3
    else:
        gcd_sum += gcd([gcd([a, b]), c]) * 6

print(gcd_sum)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
k=int(input())
 
def gcd(l,m,n):
  f=min(l,m,n)
  while l%f!=0 or m%f!=0 or n%f!=0:
    f=f-1
  return f
 
sum=0
for l in range(1,k+1):
  for m in range(l,k+1):
    for n in range(m,k+1):
      if l==m==n:
        sum=sum+gcd(l,m,n)
      elif l==m or m==n:
        sum=sum+gcd(l,m,n)*3
      else:
        sum=sum+gcd(l,m,n)*6
 
print(sum)

Submission status: Accepted

Solution code:
def readInts():
  return list(map(int,input().split()))
mod = 10**9 + 7
def gcd(a,b):
  if b == 0:
    return a
  return gcd(b, a % b)
def main():
  k = int(input())
  ans = 0
  for a in range(1,k+1):
    for b in range(1,k+1):
      for c in range(1,k+1):
        ans += gcd(a,gcd(b,c))
  print(ans)
if __name__ == '__main__':
  main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
k = int(input())

def gcd_(a, b):
    if a < b:
        a, b = b, a
    while not a % b == 0:
        a, b = b, a % b
    return b

s = 0
for i in range(1, k + 1):
    for j in range(1, k + 1):
        p = gcd_(i, j)
        if p == 1:
            s += k
        else:
            for h in range(1, k + 1):
                s += gcd_(p, h)
            
print(s)

Submission status: Accepted

Solution code:
from math import gcd

a = int(input())

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


print(ans)

Submission status: Accepted

Solution code:
import math

n = int(input())
sums = 0
for k in range(1,n+1):
    for l in range(1,n+1):
        a =math.gcd(k,l)
        for p in range(1,n+1):
            sums += math.gcd(a,p)

print(sums)

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

Submission status: Accepted

Solution code:
from math import gcd

k = int(input()) + 1
ans = 0

for s in range(1, k):
    for t in range(s, k):
        first = gcd(s, t)
        for u in range(t, k):
            if (v := len(set([s, t, u]))) == 1:
                ans += gcd(first, u)
            elif v == 2:
                ans += gcd(first, u) * 3
            else:
                ans += gcd(first, u) * 6
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from functools import lru_cache

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


@lru_cache(maxsize=None)
def solve(x, y):
    return math.gcd(x, y)


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

    ans = 0
    for i in range(1, N + 1):
        for j in range(1, N + 1):
            x = math.gcd(i, j)
            for k in range(1, N + 1):
                ans += math.gcd(x, k)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math

n = int(input())

sum = 0
memo = {'1,1':1}
for i in range(1, n+1):
  for j in range(1, n+1):
      if str(i)+','+str(j) in memo:
        ret = memo[str(i)+','+str(j)]
      elif str(j)+','+str(i) in memo:
        ret = memo[str(j)+','+str(i)]
      else:
        ret = math.gcd(i, j)
        memo[str(i)+','+str(j)] = ret
        memo[str(j)+','+str(i)] = ret

for i in memo.values():
  for j in range(1, n+1):
    sum += math.gcd(i, j)

print(sum)

Submission status: Accepted

Solution code:
import math 
import functools

K= int(input())
gcd_list = [ [float('INF') for i in range(K+1)] for j in range(K+1)]
#print(gcd_list)

for i in range(1,K+1):
    for j in range(1, K+1):
        gcd_list[i][j] = math.gcd(i,j)
#for g in gcd_list:
    #print(g)
mysum = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        mygcd = gcd_list[i][j]
        for k in range(1,K+1):
            mygcd2 = math.gcd(mygcd, k)
            mysum += mygcd2 
        
print(mysum)

Submission status: Accepted

Solution code:
import fractions
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 l in range(1, k + 1):
            ans += math.gcd(l, temp)

print(ans)

Submission status: Accepted

Solution code:
K=int(input())
def gcd(a,b,c):
    if a <b:
        a,b=b,a
    while a%b != 0:
        a,b= b,a%b
    if b < c:
        b,c=c,b
    while b % c != 0:
        b,c = c,b%c
    return c
x=0
for i in range(1,K+1):
    for j in range(1,K+1):

            for l in range(1,K+1):
                
                    if (i==1) or (j==1) or (l==1):
                        x+=1
                    else:
                        x += gcd(i,j,l)
print(x)

Submission status: Accepted

Solution code:
import math as fr

if __name__ == '__main__':
	 N = int(input())
	 
	 ans = 0

	 MAP = [[-1] * (N+1) for _ in range(N+1)]

	 for P in range(1,N+1):
	 	for q in range(P,N+1):
	 		p = P
	 		if P > q:
	 			p,q = q,p

	 		if MAP[p][q] == -1:
	 			g1 = fr.gcd(p,q)
	 			MAP[p][q] = g1
	 		else:
	 			g1 = MAP[p][q]

	 		for r in range(q,N+1):
	 			g = g1
	 			if g > r:
	 				g,r = r,g

	 			if MAP[g][r] == -1:
	 				g2 = fr.gcd(g,r)
	 				MAP[g][r] = g2
	 			else:
	 				g2 = MAP[g][r]

	 			if P == q and q == r:
		 			ans += g2
		 		elif P == q or q == r or r == P:
		 			ans += 3 * g2
		 		else:
		 			ans += 6 * g2
	 print(ans)

Submission status: Accepted

Solution code:
import math
from functools import reduce,lru_cache

K = int(input())

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

def calc_temp_2(k):
    temp_2 = 0
    for j in range(1,k):
        for l in range(j+1,k):
            temp_2 += gcd(k, j, l) * 2
        temp_2 += gcd(k,j)
    return temp_2

@lru_cache(maxsize=None)
def dp(k):
    if k == 1:
        return 1
    else:
        temp_1 = sum([gcd(k, i) for i in range(1,k)])
        temp_2 = calc_temp_2(k)
        return dp(k-1) + k + temp_1 * 3 + temp_2 * 3

print(dp(K))

Submission status: Accepted

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