{"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 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.\n\n## Constraints\n\n*   $1 \\le N \\le 10^6$\n*   $1 \\le Q \\le 10^5$\n*   $0 \\le A_k < N$\n*   $0 \\le B_k < N$\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $Q$\n$A_1$ $B_1$\n$A_2$ $B_2$\n$\\vdots$\n$A_Q$ $B_Q$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc182_f","tags":[],"sample_group":[["6 3\n2 1\n0 1\n1 0","2\n1\n6\n\nFor $k=1$, the graph has the following two connected components:\n\n*   A connected component with vertices $0,1,3,4$.\n*   A connected component with vertices $2,5$.\n\nThus, the answer for $k=1$ is $2$."],["11 3\n9 1\n5 3\n8 0","3\n3\n2\n\nFor $k=1$, the graph has the following three connected components:\n\n*   A connected component with vertices $0,1,3,6,10$.\n*   A connected component with vertices $2,5,7,8,9$.\n*   A connected component with vertex $4$.\n\nThus, the answer for $k=1$ is $3$."],["182 3\n61 2\n77 88\n180 55","36\n14\n9"]],"created_at":"2026-03-03 11:01:13"}}