F - Graph of Mod of Linear Editorial /

Time Limit: 6 sec / Memory Limit: 1024 MiB

配点 : 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 に対して以下の問題を解いてください。

頂点に 0 から N-1 までの番号が付けられている N 頂点 N 辺の無向グラフがあります。 i 番目の辺 (0\le i < N) は頂点 i と頂点 (A_k \times i+B_k)\ \text{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 の場合、以下の 2 つの連結成分に分けられます：

  • 頂点 0,1,3,4 からなる連結成分。
  • 頂点 2,5 からなる連結成分。

よって、k=1 の場合の答えは 2 になります。

入力例 2

11 3
9 1
5 3
8 0

出力例 2

3
3
2

k=1 の場合、以下の 3 つの連結成分に分けられます：

  • 頂点 0,1,3,6,10 からなる連結成分。
  • 頂点 2,5,7,8,9 からなる連結成分。
  • 頂点 4 からなる連結成分。

よって、k=1 の場合の答えは 3 になります。

入力例 3

182 3
61 2
77 88
180 55

出力例 3

36
14
9

Score : 1000 points

Problem Statement

You are given integers N and Q, and two integer sequences of length Q: A=(A_1,A_2,\ldots,A_Q) and B=(B_1,B_2,\ldots, B_Q).

For each k=1,2,\ldots,Q, solve the following problem:

There is an undirected graph with N vertices numbered from 0 to N-1 and N edges. The i-th edge (0 \le i < N) connects vertices i and (A_k \times i + B_k) \mod N bidirectionally. Find the number of connected components in this undirected graph.

Constraints

  • 1 \le N \le 10^6
  • 1 \le Q \le 10^5
  • 0 \le A_k < N
  • 0 \le B_k < N
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N Q
A_1 B_1
A_2 B_2
\vdots
A_Q B_Q

Output

Print Q lines. The i-th line should contain the answer for k=i.

Sample Input 1

6 3
2 1
0 1
1 0

Sample Output 1

2
1
6

For k=1, the graph has the following two connected components:

  • A connected component with vertices 0,1,3,4.
  • A connected component with vertices 2,5.

Thus, the answer for k=1 is 2.

Sample Input 2

11 3
9 1
5 3
8 0

Sample Output 2

3
3
2

For k=1, the graph has the following three connected components:

  • A connected component with vertices 0,1,3,6,10.
  • A connected component with vertices 2,5,7,8,9.
  • A connected component with vertex 4.

Thus, the answer for k=1 is 3.

Sample Input 3

182 3
61 2
77 88
180 55

Sample Output 3

36
14
9