We will analyze the problem in terms of directed graphs. The number of connected components in the undirected graph corresponds to the number of cycles in the directed graph, so we will focus on the latter.

For \(A = 0, 1\), the answer is obvious, so we will consider the case where \(A \geq 2\).

[1] When \(\gcd(N, A) \neq 1\)

Let \(f^N(x)\) represent the vertex reached after \(N\) moves starting from vertex \(x\). We have \(\displaystyle f^N(x)\equiv A^N x+B\frac{A^N-1}{A-1}\ \text{mod}\ N\).

Here, let \(d = \gcd(N, A^N)\). Then, since \(\displaystyle f^N(x+1)-f^N(x)\equiv A^N\equiv 0\ \text{mod}\ d\), the vertex numbers of the vertices forming a cycle all match \(f^N(0)\) modulo \(d\). Considering only these vertices, the equation \(\displaystyle dk_2+f^N(0)\equiv A(dk_1+f^N(0))+B\ \text{mod}\ N\) reduces to \(\displaystyle k_2\equiv Ak_1+\frac{A^N}{d}B\ \text{mod}\ \frac{N}{d}\), so this problem can be reduced to the case where \(\displaystyle (N, A, B)\leftarrow\left(\frac{N}{d}, A \mod \frac{N}{d}, \frac{A^N}{d}B \mod \frac{N}{d}\right)\).

By performing this substitution, the problem can be reduced to the case where \(\gcd(N, A) = 1\).

[2] When \(\gcd(N, A) = 1\)

If \(\gcd(N, A) = 1\), all vertices form some cycle. Therefore, the answer is the sum of the reciprocals of the lengths of the cycles formed by each vertex.

If vertex \(x\) returns to its original position after \(K\) moves, then \(\displaystyle A^Kx+B\frac{A^K-1}{A-1}\equiv x\ \text{mod}\ N\), which implies \(\displaystyle A^K\equiv 1\ \text{mod}\ \frac{N(A-1)}{\gcd(N(A-1), (A-1)x+B)}\). Letting \(\displaystyle G=\gcd(A-1, B)\), \(A'=\frac{A-1}{G}\), \(B'=\frac{B}{G}\), and \(N'=\frac{N}{\gcd(A'^N, N)}\), we have \(\displaystyle \gcd(N(A-1), (A-1)x+B)=G\gcd(N', A'x+B')\). Since \(A'\) and \(N'\) are coprime, for each \(0\le y<N'\), there exist exactly \(\displaystyle \frac{N}{N'}\) values \(0\le x<N\) such that \(y\equiv A'x+B'\ \text{mod}\ N'\). Therefore, if we let \(C_y\) be the smallest positive integer \(K\) such that \(\displaystyle A^K\equiv 1\ \text{mod}\ \frac{NA'}{\gcd(y, N')}\) for each \(0\le y<N'\), the desired answer is \(\displaystyle \frac{N}{N'}\sum_{y=0}^{N'-1}\frac{1}{C_y}\).

Values of \(y\) with the same \(\gcd(y, N')\) have the same \(C_y\). Therefore, for each divisor \(n\) of \(N'\), we need to find the answer for \(n = \gcd(y, N')\), and sum them up. The number of values \(0\le y<N'\) such that \(n = \gcd(y, N')\) is \(\displaystyle \phi\left(\frac{N'}{n}\right)\), so the answer can be expressed as \(\displaystyle \frac{N}{N'}\sum_{n| N'}\frac{1}{C_n}\phi\left(\frac{N'}{n}\right)\). Here, \(\phi\) is the Euler’s totient function.

To compute \(C_n\) for each \(n\), we can use the following two facts to compute them in ascending order of \(n\):

• By Euler’s theorem, the candidates for \(C_1\) are divisors of \(\phi(NA')\).
• Let \(n_1\) and \(n_2\) be divisors of \(N'\). If \(n_1\) divides \(n_2\), then \(C_{n_2}\) divides \(C_{n_1}\).

This can be easily implemented using a DFS-like method.

The value of \(\phi(NA')\) and its prime factorization can be computed quickly by precomputing the prime factorizations of all positive integers up to \(N\).

By implementing the above appropriately, you can solve this problem.

Sample Implementation (Python3)