Observations

Instead of recurrence relations \(s_n = As_{n-1} + Bs_{n-2}\), let us define the sequence by \(s_n = (As_{n-1} + Bs_{n-2}) \bmod{M}\). The new sequence has exactly the same remainder modulo \(M\). All the elements are between \(0\) and \(M-1\), and the criteria in the problem statement reduces to simply having no \(0\) in the sequence. From now on, let \(s\) refer to this new sequence.

Consider an automaton that takes integer pairs \((x, y)\) with \(0 \leq x, y \leq M-1\) as the states. Transitions occur from state \((x, y)\) only to \((y, (Ay + Bx) \bmod{M})\). This transition corresponds to “sliding the window” of two elements, from \((s_{n-2}, s_{n-1})\) to \((s_{n-1}, s_{n-0})\).

Regardless of the initial values \(s_1\) and \(s_2\), if you start from state \((s_{1}, s_{2})\) in the automaton and transition \((k-1)\) times, you will reach state \((s_{k}, s_{k+1})\). Thus, \(s\) contains \(0\) if and only if you can reach a state from \((s_{1}, s_{2})\) to \((0, t)\) (where \(t\) is arbitrary) with some transitions. Therefore, if we can determine for all \(M^2\) pairs \((x, y)\) if state \((s_1, s_2) = (x, y)\) satisfies this condition, the sought count can be obtained as the complement.

Let \(M\) be the set of state \((0, t)\) (where \(t\) is arbitrary).

If we regard the states and transitions as the vertices and edges of a directed graph, it is reduced to determining for each vertex \(v\) if there exists a path from \(v\) to any vertex \(w \in W\). If we reverse the edges in the graph, the criteria is simply reduced to the reachability from any vertex \(w \in W\) to that vertex \(v\), and the results can be obtained at once with a search like BFS (Breadth-First Search) or DFS (Depth-First Search).

The time complexity is \(O(M^2)\), which is fast enough.

Sample code (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;
}