{"problem":{"name":"ZHY 的生成树","description":{"content":"ZHY 有一个 $n$ 个点的完全图，点 $u$ 与点 $v$ 的距离为 $\\gcd(u,v)$，求这个完全图的最大生成树的边权之和。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1500,"memory_limit":131072},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9488"},"statements":[{"statement_type":"Markdown","content":"ZHY 有一个 $n$ 个点的完全图，点 $u$ 与点 $v$ 的距离为 $\\gcd(u,v)$，求这个完全图的最大生成树的边权之和。\n\n## Input\n\n一个正整数 $n$。\n\n## Output\n\n一个整数，表示这个最大生成树的边权之和。\n\n[samples]\n\n## Note\n\n**本题采用捆绑测试。**\n\n$\\text{Subtask}$ $0\\kern{3pt}$(10pts)：$n\\le 5$。\n\n$\\text{Subtask}$ $1\\kern{3pt}$(20pts)：$n\\le 1000$。\n\n$\\text{Subtask}$ $2\\kern{3pt}$(30pts)：$n\\le 10^{6}$。\n\n$\\text{Subtask}$ $3\\kern{3pt}$(40pts)：$n\\le 10^{7}$。\n\n对于所有测试数据，$1\\le n \\le 10^{7}$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9488","tags":["O2优化"],"sample_group":[["4","4"],["30","183"],["100","1916"]],"created_at":"2026-03-03 11:09:25"}}