Edit

【pythonでABC162を解説】C - Sum of gcd of Tuples (Easy)

問題概要

問題ページ

C - Sum of gcd of Tuples (Easy)
C - Sum of gcd of Tuples (Easy)

問題ページへ移動する

問題文

\(\displaystyle{\sum_{a=1}^{K}\sum_{b=1}^{K}\sum_{c=1}^{K} \gcd(a,b,c)}\) を求めてください。

ただし、\(\gcd(a,b,c)\) は \(a,b,c\) の最大公約数を表します。

制約

  • \(1 \leq K \leq 200\)
  • \(K\) は整数

問題の考察

ACコード

import sys
import math


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    k = int(input().rstrip('\n'))
    t = 0
    for i in range(1, k + 1):
        for j in range(1, k + 1):
            for l in range(1, k + 1):
                t += math.gcd(math.gcd(i, j), l)
    print(t)


if __name__ == '__main__':
    solve()

-Edit