「VUSC」Math Game

Luogu
IDLGP8954
Time5000ms
Memory512MB
DifficultyP5
数学并查集深度优先搜索 DFS
Farmer John 有一个集合 $S$,集合初始为 $\{2,3,4,...,N\}$。 对于两个**在集合 $S$ 内的**正整数 $p,q$,我们称它们为「一对好数」当且仅当 $p^k=q(k\ge 2\land k\in\N)$。 我们将每个 $S$ 中的数看成一张**无向图**中的节点,对于每一对「好数」,我们在这两个数间连一条无向边。 Farmer John 会进行 $Q$ 次操作,操作有以下两种: 1. 给出 $x$,询问结点 $x$ 所在的连通块大小。 2. 给出 $x$,从 $S$ 中移除 $x$。**与此同时,无向图中的结点 $x$ 也被移除。** 由于 Bessie 的速度太慢了,她想要你来帮忙。 ## Input 第 $1$ 行 $2$ 个正整数,$N,Q$。 接下来 $Q$ 行,每行一个正整数,$op_i,x_i$。 其中,$op_i$ 表示操作的序号。 **数据保证 $x_i$ 在集合 $S$ 中**。 ## Output 对于操作 $1$,每行输出一个正整数,表示询问的答案。 [samples] ## Background **upd 2023.1.22**:新增一组 Hack 数据 by @[MCRS_lizi](https://www.luogu.com.cn/user/585805)。 远在哞利坚的 Bessie 也要在新春之际走亲访友!为了打发时间,她常和 Farmer John 玩一个有趣的数字游戏。 ## Note #### 【样例解释】 这是原始无向图(上面一排都是孤点): ![](https://cdn.luogu.com.cn/upload/image_hosting/utsz04dt.png) 这是进行第一次操作 $2$ 后的无向图(删除了结点 $9$): ![](https://cdn.luogu.com.cn/upload/image_hosting/wmexc9ks.png) 这是进行第二次操作 $2$ 后的无向图(删除了结点 $2$): ![](https://cdn.luogu.com.cn/upload/image_hosting/9mi0l18p.png) --- #### 【数据范围】 全部数据满足: - $2\le N \le 10^{18}$ - $1\le Q \le 10^6$ - $x_i\in S$ - $op_i \in \{1,2\}$ 测试点 $1\sim2$ 另外满足 $2\le N \le 10^5$,$1\le Q \le 10^4$。 测试点 $3\sim4$ 另外满足所有 $x_i=m^{p_i}$,其中 $m$ 为一满足 $m\ge 2 \land m\in \N$ 的**常数**。 测试点 $5\sim10$ 没有额外限制。
Samples
Input #1
30 6
1 6
1 4
2 9
1 3
2 2
1 16
Output #1
1
4
2
2
API Response (JSON)
{
  "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$ 次...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments