ABC 162 C問題

Question

前提・実現したいこと

TLEを無くしたい

発生している問題・エラーメッセージ

TLE
mathのgcdを使ったら通りました。違いがわからないので教えていただきたいです。

該当のソースコード

K = int(input())
ans = 0

def gcd(p, q):
  if p % q == 0: return q
  return gcd(q, p%q)

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)  

Answer 1

単純な話で、math.gcdの実装はC言語で書かれているから高速です。

どうしても自前のgcdで頑張るなら、関数の実行結果をキャッシュするlru_cacheを利用したらどうでしょうか。

from functools import lru_cache
K = int(input())
ans = 0

@lru_cache(maxsize = None)
def gcd(p, q):
    r = p % q
    if r == 0:
        return q
    return gcd(q, r)

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,nohit)  

手前の計測ではmath.gcd版よりも多少高速です。