結果

問題 No.2249 GCDistance
コンテスト
ユーザー 👑 seekworser
提出日時 2024-01-07 17:55:21
言語 Nim
(2.2.10 + ACL)
コンパイル:
nim --nimcache=~ --hints:off -o:a.out -d:release cpp _filename_
実行:
./a.out
結果
AC  
実行時間 443 ms / 5,000 ms
+ 284µs
コード長 1,171 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,328 ms
コンパイル使用メモリ 69,388 KB
実行使用メモリ 171,004 KB
最終ジャッジ日時 2026-09-05 08:20:22
合計ジャッジ時間 11,121 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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