AT_arc182_f [ARC182F] Graph of Mod of Linear

给定整数 $N, Q$，以及长度为 $Q$ 的整数列 $A=(A_1, A_2, \ldots, A_Q), B=(B_1, B_2, \ldots, B_Q)$。 对于 $k=1,2,\ldots,Q$，请你解决以下问题： > 有一个无向图，包含 $N$ 个顶点，顶点编号为 $0$ 到 $N-1$，共有 $N$ 条边。第 $i$ 条边（$0 \leq i < N$）连接顶点 $i$ 和顶点 $(A_k \times i + B_k) \bmod N$。请你求出该无向图的连通分量数。

输入以如下格式从标准输入给出。 > $N$ $Q$ $A_1$ $B_1$ $A_2$ $B_2$ > $\vdots$ > $A_Q$ $B_Q$

输出 $Q$ 行。第 $i$ 行输出 $k=i$ 时的答案。

## 限制条件 - $1 \leq N \leq 10^6$ - $1 \leq Q \leq 10^5$ - $0 \leq A_k < N$ - $0 \leq B_k < N$ - 所有输入均为整数 ## 样例解释 1 对于 $k=1$，可以分为以下 $2$ 个连通分量： - 包含顶点 $0,1,3,4$ 的连通分量。 - 包含顶点 $2,5$ 的连通分量。 因此，$k=1$ 时的答案为 $2$。 ## 样例解释 2 对于 $k=1$，可以分为以下 $3$ 个连通分量： - 包含顶点 $0,1,3,6,10$ 的连通分量。 - 包含顶点 $2,5,7,8,9$ 的连通分量。 - 包含顶点 $4$ 的连通分量。 因此，$k=1$ 时的答案为 $3$。 由 ChatGPT 4.1 翻译