解説同様、頂点 \((i,j)\to (j,(A\times j+B\times i)\pmod M)\) に辺を張ったfunctional graph を考えます。またそれぞれの頂点 \((i,j)\) に

\[ C_{i,j} = \begin{cases} 1 & (i=0 \ \text{または}\ j=0) \\ 0 & (\text{otherwise}) \end{cases} \]

のように値を書きます。このとき、\((i,j)\) から無限回辺をたどったときに通った頂点（ \((i,j)\) を含む ）に書かれた数字の総和が \(0\) \(\iff\) \((x,y)=(i,j)\) のときに数列が \(M\) の倍数を全く含まないとなります。

functional graph の性質から \((i,j)\) から十分大きい回数（ 具体的には \(M^2\) 回以上 ）辺をたどった時の総和を計算すれば十分で、この総和はダブリングと同じ要領で計算でき、\(O(M^2\log M)\) で問題を解くことができます。

実装 (C++ 144ms)