{"problem":{"name":"「VUSC」Math Game","description":{"content":"Farmer John 有一个集合 $S$，集合初始为 $\\{2,3,4,...,N\\}$。 对于两个**在集合 $S$ 内的**正整数 $p,q$，我们称它们为「一对好数」当且仅当 $p^k=q(k\\ge 2\\land k\\in\\N)$。 我们将每个 $S$ 中的数看成一张**无向图**中的节点，对于每一对「好数」，我们在这两个数间连一条无向边。 Farmer John 会进行 $Q$ 次","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":5000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8954"},"statements":[{"statement_type":"Markdown","content":"Farmer John 有一个集合 $S$，集合初始为 $\\{2,3,4,...,N\\}$。\n\n对于两个**在集合 $S$ 内的**正整数 $p,q$，我们称它们为「一对好数」当且仅当 $p^k=q(k\\ge 2\\land k\\in\\N)$。\n\n我们将每个 $S$ 中的数看成一张**无向图**中的节点，对于每一对「好数」，我们在这两个数间连一条无向边。\n\nFarmer John 会进行 $Q$ 次操作，操作有以下两种：\n\n1. 给出 $x$，询问结点 $x$ 所在的连通块大小。\n2. 给出 $x$，从 $S$ 中移除 $x$。**与此同时，无向图中的结点 $x$ 也被移除。**\n\n由于 Bessie 的速度太慢了，她想要你来帮忙。\n\n## Input\n\n第 $1$ 行 $2$ 个正整数，$N,Q$。\n\n接下来 $Q$ 行，每行一个正整数，$op_i,x_i$。\n其中，$op_i$ 表示操作的序号。\n\n**数据保证 $x_i$ 在集合 $S$ 中**。\n\n## Output\n\n对于操作 $1$，每行输出一个正整数，表示询问的答案。\n\n[samples]\n\n## Background\n\n**upd 2023.1.22**：新增一组 Hack 数据 by @[MCRS_lizi](https://www.luogu.com.cn/user/585805)。\n\n远在哞利坚的 Bessie 也要在新春之际走亲访友！为了打发时间，她常和 Farmer John 玩一个有趣的数字游戏。\n\n## Note\n\n#### 【样例解释】\n\n这是原始无向图（上面一排都是孤点）：\n![](https://cdn.luogu.com.cn/upload/image_hosting/utsz04dt.png)\n\n这是进行第一次操作 $2$ 后的无向图（删除了结点 $9$）：\n![](https://cdn.luogu.com.cn/upload/image_hosting/wmexc9ks.png)\n\n这是进行第二次操作 $2$ 后的无向图（删除了结点 $2$）：\n![](https://cdn.luogu.com.cn/upload/image_hosting/9mi0l18p.png)\n\n---\n\n#### 【数据范围】\n\n全部数据满足：\n- $2\\le N \\le 10^{18}$\n- $1\\le Q \\le 10^6$\n- $x_i\\in S$\n- $op_i \\in \\{1,2\\}$\n\n测试点 $1\\sim2$ 另外满足 $2\\le N \\le 10^5$，$1\\le Q \\le 10^4$。\n\n测试点 $3\\sim4$ 另外满足所有 $x_i=m^{p_i}$，其中 $m$ 为一满足 $m\\ge 2 \\land m\\in \\N$ 的**常数**。\n\n测试点 $5\\sim10$ 没有额外限制。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8954","tags":["数学","并查集","深度优先搜索 DFS"],"sample_group":[["30 6\n1 6\n1 4\n2 9\n1 3\n2 2\n1 16","1\n4\n2\n2"]],"created_at":"2026-03-03 11:09:25"}}