Graph of Mod of Linear

AtCoder

IDarc182_f

Time6000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

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$.

Input #2

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$.

Input #3

Output #3

36
14
9

API Response (JSON)

{
  "problem": {
    "name": "Graph of Mod of Linear",
    "description": {
      "content": "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",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 6000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc182_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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)$.\nFor each $k=1,2,\\ldots,Q$, solve the following problem:\n\n> There is...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments