結果

問題 No.2249 GCDistance
ユーザー 👑 seekworserseekworser
提出日時 2024-01-07 17:55:21
言語 Nim
(2.0.2)
結果
AC  
実行時間 1,374 ms / 5,000 ms
コード長 1,171 bytes
コンパイル時間 3,233 ms
コンパイル使用メモリ 65,608 KB
実行使用メモリ 171,992 KB
最終ジャッジ日時 2024-01-07 17:55:44
合計ジャッジ時間 21,552 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,226 ms
160,404 KB
testcase_01 AC 1,345 ms
171,408 KB
testcase_02 AC 1,347 ms
171,408 KB
testcase_03 AC 1,326 ms
171,992 KB
testcase_04 AC 1,258 ms
165,012 KB
testcase_05 AC 1,346 ms
171,408 KB
testcase_06 AC 1,324 ms
171,716 KB
testcase_07 AC 1,340 ms
171,992 KB
testcase_08 AC 1,209 ms
160,788 KB
testcase_09 AC 1,337 ms
171,408 KB
testcase_10 AC 1,374 ms
171,408 KB
権限があれば一括ダウンロードができます

ソースコード

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