← 返回题目列表

AtCoder · arc182_f

F. 线性模图

中文机器翻译题面 查看原题

分数: 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