有向グラフにして考えます。無向グラフの連結成分と有向グラフでの閉路の個数は一致するので、以降は後者を考えます。

\(A=0,1\) の場合の答えは明らかなので以降は \(A\geq 2\) であるとします。

[1] \(\gcd(N,A)\neq 1\) である場合

頂点 \(x\) から \(N\) 回移動した先の頂点を \(f^N(x)\) と表すと、 \(\displaystyle f^N(x)\equiv A^N x+B\frac{A^N-1}{A-1}\ \text{mod}\ N\) となります。

ここで、 \(d=\gcd(N,A^N)\) とします。すると、 \(\displaystyle f^N(x+1)-f^N(x)\equiv A^N\equiv 0\ \text{mod}\ d\) より、閉路を構成する頂点の頂点番号は全て \(\mathrm{mod}\ d\) で \(f^N(0)\) と一致します。これらの頂点のみを考えると、 \(dk_2+f^N(0)\equiv A(dk_1+f^N(0))+B\ \text{mod}\ N\) は \(\displaystyle k_2\equiv Ak_1+\frac{A^N}{d}B\ \text{mod}\ \frac Nd\) となるので、この問題は \(\displaystyle (N,A,B)\leftarrow\left(\frac Nd,A\ \mathrm{mod}\ \frac Nd, \frac{A^N}dB\ \mathrm{mod}\ \frac Nd\right)\) の場合に帰着します。

この置き換えにより、この問題は \(\gcd(N,A)=1\) の場合に帰着させることができます。

[2] \(\gcd(N,A)=1\) である場合

\(\gcd(N,A)=1\) の場合、全ての頂点がいずれかの閉路を構成します。よって、各頂点に対してその頂点が構成する閉路の長さの逆数の和が答えとなります。

頂点 \(x\) が \(K\) 回で元の場所に戻ってくるとすると \(\displaystyle A^Kx+B\frac{A^K-1}{A-1}\equiv x\ \text{mod}\ N\) 、つまり \(\displaystyle A^K\equiv 1\ \text{mod}\ \frac{N(A-1)}{\gcd(N(A-1),(A-1)x+B)}\) が成り立ちます。 \(\displaystyle G=\gcd(A-1,B),\ A'=\frac{A-1}G,\ B'=\frac BG,\ N'=\frac{N}{\gcd(A'^{N}, N)}\) とすると、 \(\displaystyle \gcd(N(A-1),(A-1)x+B)=G\gcd(N',A'x+B')\) が成立します。 \(A'\) と \(N'\) は互いに素なので、各 \(0\le y < N'\) に対し \(y\equiv A'x+B'\ \text{mod}\ N'\) を満たす \(0\le x<N\) がちょうど \(\displaystyle \frac N{N'}\) 個ずつ存在します。よって、 \(0\le y<N'\) に対し \(\displaystyle A^K\equiv 1\ \text{mod}\ \frac{NA'}{\gcd(y,N')}\) を満たす最小の正整数 \(K\) を \(C_y\) とすると、求める答えは \(\displaystyle \frac N{N'}\sum_{y=0}^{N'-1}\frac1{C_y}\) となります。

\(\gcd(y,N')\) が同じであれば \(C_y\) も同じ値になります。よって、各 \(N'\) の約数 \(n\) に対して \(n=\gcd(y,N')\) の場合の答えを求め、まとめて足し上げれば良いです。 \(n=\gcd(y,N')\) を満たす \(0\le y < N'\) の個数は \(\displaystyle \phi\left(\frac{N'}n\right)\) 個なので、答えは \(\displaystyle \frac N{N'}\sum_{n| N'}\frac1{C_n}\phi\left(\frac{N'}n\right)\) と表せます。ここで、 \(\phi\) は オイラーのトーシェント関数 です。

各 \(n\) に対して \(C_n\) を計算していく方法ですが、以下の \(2\) つの事実を用いて \(n\) の昇順に求めていけば良いです：

• オイラーの定理より \(C_1\) の 候補は \(\phi(NA')\) の約数になる。
• \(n_1,n_2\) を \(N'\) の約数とする。この時、 \(n_1\) が \(n_2\) の約数なら \(C_{n_2}\) は \(C_{n_1}\) の約数になる。

DFS の要領で計算していくと楽に実装することができます。

\(\phi(NA')\) とその素因数分解は \(N\) 以下の全ての正整数の素因数分解を事前に計算しておくことで高速に計算することができます。

以上を適切に実装することでこの問題を解くことができます。

実装例(Python3)