結果

問題 No.2249 GCDistance
コンテスト
ユーザー seekworser
提出日時 2024-01-07 17:55:21
言語 Nim
(2.2.0)
結果
AC  
実行時間 1,468 ms / 5,000 ms
コード長 1,171 bytes
コンパイル時間 3,302 ms
コンパイル使用メモリ 65,912 KB
実行使用メモリ 171,752 KB
最終ジャッジ日時 2024-09-27 19:28:29
合計ジャッジ時間 23,521 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

import macros;macro ImportExpand(s:untyped):untyped = parseStmt($s[2])
import strutils
import sequtils
ImportExpand "cplib/math/euler_phi.nim" <=== "when not declared CPLIB_MATH_EULER_PHI:\n    const CPLIB_MATH_EULER_PHI* = 1\n    import sequtils\n    proc euler_phi*(n: int): int =\n        result = n\n        var n = n\n        for i in 2..<n:\n            if i*i > n:\n                break\n            if n mod i == 0:\n                result -= result div i\n                while n mod i == 0:\n                    n = n div i\n        if n > 1:\n            result -= result div n\n\n    proc euler_phi_list*(n: int): seq[int] =\n        result = (0..n).toSeq\n        for i in 2..n:\n            if result[i] == i:\n                for j in countup(i, n, i):\n                    result[j] = result[j] div i\n                    result[j] *= (i - 1)\n    discard\n"


var t = stdin.readLine.parseint
var mx = 10000000
var li = euler_phi_list(mx)
var dp = newSeqWith(mx+1, 0)
for i in 2..mx:
    dp[i] = dp[i-1] + li[i] * 1 + (i - 1 - li[i]) * 2
var ans = newSeq[int](0)
for _ in 0..<t:
    var n = stdin.readLine.parseint
    ans.add(dp[n])
echo ans.join("\n")
0