考察

漸化式 \(s_n = As_{n-1} + Bs_{n-2}\) を \(s_n = (As_{n-1} + Bs_{n-2}) \bmod{M}\) で置き換えて得られる数列を考えます．この数列と元の数列は，各要素を \(\mod{M}\) のもとで比較すれば等しいです．この数列の要素はすべて \(0\) 以上 \(M-1\) 以下であり，問題文中の条件はこの数列が \(0\) を含むことと言い換えられます．以下ではこの数列を \(s\) として扱います．

\(0 \leq x, y \leq M-1\) の範囲の整数組 \((x, y)\) を状態にもつオートマトンをおき，状態 \((x, y)\) からは状態 \((y, (Ay + Bx) \bmod{M})\) にのみ遷移するとします．これは，数列 \(s\) の任意の位置にある連続 \(2\) 要素 \((s_{n-2}, s_{n-1})\) に対する「\(1\) つ次の位置」の連続 \(2\) 要素 \((s_{n-1}, s_{n-0})\) に対応します．

\(M = 4,\ A = 1,\ B = 2\) のとき (入力例 1) のオートマトンを以下の図に示します．

このとき，どのような初期値 \(s_1, s_2\) をもつ数列 \(s\) においても，オートマトン上で状態 \((s_{1}, s_{2})\) から \(k-1\) 回遷移した先は状態 \((s_{k}, s_{k+1})\) です．ここから，\(s\) が \(0\) を含むことは，状態 \((s_{1}, s_{2})\) から任意回の遷移で状態 \((0, t)\) (\(t\) は任意) にたどり着けることとして言い換えられます．したがって，状態 \((s_1, s_2) = (x, y)\) がこれを満たすかどうかを \(M^2\) 通りの \((x, y)\) すべてについて判定できれば，満たさないものの個数が答えとなります．

状態 \((0, t)\) (\(t\) は任意) からなる集合を \(W\) とおきます．

オートマトンの状態・遷移を有向グラフの頂点・辺として見たとき，各頂点 \(v\) について，そこから集合 \(W\) 内のいずれかの頂点 \(w \in W\) にたどり着くパスが存在するかを判定できればよいです．これは，辺の向きを逆にした有向グラフ上で，\(W\) 内のいずれかの頂点 \(w \in W\) からその頂点 \(v\) にたどり着くパスが存在するかどうかとして言い換えられ，BFS や DFS といった探索によってまとめて結果を得ることができます．

時間計算量は \(O(M^2)\) となり，十分高速です．

実装例 (C++)

#include <iostream>
using std::cin;
using std::cout;
#include <string>
using std::string;
#include <algorithm>
#include <vector>
using std::vector;
#include <queue>
using std::queue;

typedef long long int ll;

ll m, a, b;

vector<vector<ll> > edges;
vector<ll> isseen;
void solve () {
	// backward edges
	edges.resize(m*m);
	for (ll i = 0; i < m; i++) {
		for (ll j = 0; j < m; j++) {
			// (i, j) <- (j, i*b+j*a)
			ll k = (i * b + j * a) % m;
			edges[j * m + k].push_back(i * m + j);
		}
	}

	// bfs init
	isseen.assign(m*m, 0);
	queue<ll> que;
	for (ll i = 0; i < m; i++) {
		for (ll j = 0; j < m; j++) {
			if (i == 0 || j == 0) {
				ll v = i*m + j;
				isseen[v] = 1;
				que.push(v);
			}
		}
	}
	// bfs run
	while (!que.empty()) {
		ll v = que.front();
		que.pop();

		for (ll u : edges[v]) {
			if (!isseen[u])	{
				isseen[u] = 1;
				que.push(u);
			}
		}
	}

	// count answers
	ll ans = 0;
	for (ll i = 0; i < m; i++) {
		for (ll j = 0; j < m; j++) {
			if (isseen[i * m + j] == 0) ans++;
		}
	}
	
	cout << ans << "\n";

}

int main (void) {
	std::cin.tie(nullptr);
	std::ios_base::sync_with_stdio(false);

	cin >> m >> a >> b;
	
	solve();

	return 0;
}