{"problem":{"name":"[蓝桥杯 2023 省 A] 翻转硬币","description":{"content":"给定 $n$ 个按顺序摆好的硬币，一开始只有第 $1$ 个硬币朝下，其他硬币均朝上。你每次操作可以选择任何一个整数 $i$ 并将所有满足 $j \\bmod i=0$ 的位置 $j$ 的硬币翻转。 求最少需要多少次操作可以让所有硬币都朝上。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9238"},"statements":[{"statement_type":"Markdown","content":"给定 $n$ 个按顺序摆好的硬币，一开始只有第 $1$ 个硬币朝下，其他硬币均朝上。你每次操作可以选择任何一个整数 $i$ 并将所有满足 $j \\bmod i=0$ 的位置 $j$ 的硬币翻转。\n\n求最少需要多少次操作可以让所有硬币都朝上。\n\n## Input\n\n输入一行包含一个整数 $n$。\n\n## Output\n\n输出一行包含一个整数表示最少需要的操作次数。\n\n[samples]\n\n## Note\n\n#### 【评测用例规模与约定】\n\n对于 $30 \\%$ 的评测用例，$n \\leq 5 \\times 10^6$；\n\n对于 $70 \\%$ 的评测用例，$n \\leq 10^9$；\n\n对于所有评测用例，$1 \\leq n \\leq 10^{18}$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9238","tags":["2023","O2优化","素数判断,质数,筛法","蓝桥杯省赛"],"sample_group":[["7","6"],["1131796","688042"]],"created_at":"2026-03-03 11:09:25"}}