分数: 1000 点
问题陈述
给你整数 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 to N-1 和 N 边缘。的 i第边缘 (0 \le i < N) 连接顶点 i 和 (A_k \times i + B_k) \mod N 双向。求这个无向图中连通分量的数量。
约束
- 1 \le N \le 10^6
- 1 \le Q \le 10^5
- 0 \le A_k < N
- 0 \le B_k < N
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N Q A_1 B_1 A_2 B_2 \vdots A_Q B_Q
输出
打印 Q 行。 的 i- 第行应包含以下问题的答案 k=i.
示例输入 1
6 3 2 1 0 1 1 0
示例输出 1
2 1 6
对于 k=1,该图具有以下两个连通分量:
- 具有顶点的连通组件 0,1,3,4.
- 具有顶点的连通组件 2,5.
因此,答案 k=1 is 2.
示例输入 2
11 3 9 1 5 3 8 0
示例输出 2
3 3 2
对于 k=1,该图具有以下三个连通分量:
- 具有顶点的连通组件 0,1,3,6,10.
- 具有顶点的连通组件 2,5,7,8,9.
- 具有顶点的连通分量 4.
因此,答案 k=1 is 3.
示例输入 3
182 3 61 2 77 88 180 55
示例输出 3
36 14 9