{"problem":{"name":"『JROI-4』分数","description":{"content":"“$x$ 人血书”的过程可以看成一个函数 $f(x)$： 有一个 $\\frac{0}{x}$ 的分数。重复以下步骤直到这个分数为 $1$： 1. 分子 $+1$。 2. 如果这个分数可以约分，约分到最简形式。 现在小 D 给了你 $T$ 组数据，每组数据都是给定 $n$，求在 $1\\le x\\le n$ 的情况下 $f(x)$ 的最大操作次数。 但是他太菜了，不会，你能帮帮他吗？","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8319"},"statements":[{"statement_type":"Markdown","content":"“$x$ 人血书”的过程可以看成一个函数 $f(x)$：\n\n有一个 $\\frac{0}{x}$ 的分数。重复以下步骤直到这个分数为 $1$：\n\n1. 分子 $+1$。\n2. 如果这个分数可以约分，约分到最简形式。\n\n现在小 D 给了你 $T$ 组数据，每组数据都是给定 $n$，求在 $1\\le x\\le n$ 的情况下 $f(x)$ 的最大操作次数。\n\n但是他太菜了，不会，你能帮帮他吗？\n\n## Input\n\n第一行一个正整数 $T$。\n\n接下来 $T$ 行，每行一个正整数 $n$。\n\n## Output\n\n共 $T$ 行，每行一个整数 $s$ 表示在 $1\\le x\\le n$ 的情况下 $f(x)$ 的最大操作次数。\n\n[samples]\n\n## Background\n\n在 QQ 群中，经常会出现这样的接龙：\n- 万人血书 xxx（1/10000）$\\to$\n- 万人血书 xxx（1/5000）$\\to$\n- 万人血书 xxx（1/2500）$\\to$\n- 万人血书 xxx（1/1250）$\\to \\dots$\n\n以此类推，在可以约分的情况下，“万人血书”很快就能完成。\n\n## Note\n\n### 样例解释\n\n$f(1)=1,f(2)=2,f(3)=3,f(4)=3,f(5)=5$。\n\n我也想把更大的 $f(x)$ 列出来，但是地方不够了。\n\n### 数据范围\n\n对于全部数据，$1\\le T\\le 5\\times 10^5$，$1\\le n\\le 2\\times 10^6$。\n\nSubtask 中没填的部分表示和全部数据的范围一样。\n\n| 子任务编号 | $T$ 的范围 | $n$ 的范围 | 特殊性质 |分值|\n| -----------: | -----------: | -----------: | -----------: |-----------: |\n| Subtask $1$ | $T\\le 3$ | $n\\le 10$ |  |$10$|\n| Subtask $2$ | $T\\le 5$ | $n\\le 10^3$ |  |$30$|\n| Subtask $3$ |  |  | $n$ 为质数|$10$|\n| Subtask $4$  |  | $n\\le 5\\times 10^5$ |  |$20$|\n| Subtask $5$  |  |  |  |$30$|","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8319","tags":["数学","2022","洛谷原创","素数判断,质数,筛法","洛谷月赛"],"sample_group":[["5\n1\n2\n5\n8\n114514","1\n2\n5\n7\n114493\n"]],"created_at":"2026-03-03 11:09:25"}}