この問題はBaby Step Giant Stepと呼ばれる手法を用いることで、1ケースあたり \(O(\sqrt{P}\log{P})\) で解くことができます。

Baby step Giant stepについて

Baby step Giant step とは \(f,x,y\) が与えられたとき、\(f^n(x)=y\) となる最小の \(n\) を求めるアルゴリズムです。
適当な定数 \(M\) をとり、\(i=0,1,2,\ldots\) の順に「\(f^{iM+j}(x)=y\) を満たす \(0\leq j< M\) は存在するか、存在するなら最小値は？」という問題を解くことで元の問題に答えます。
この小問題は、\(f^{-1}\) が存在するときには「\(f^{iM}(x)=(f^{-1})^j(y)\) となる \(0\leq j< M\) は存在するか、存在するなら最小値は？」と読み替えることができ、予め右辺の候補を列挙しておくことで各 \(i\) に対して高速に判定できる、というのがこのアルゴリズムの基本的なアイディアです。

本問題の解法

\(A=0\) のとき答えを求めることは容易です。\(A\neq 0\) の場合を考えます。このとき、もし \(X_n=T\) となる \(n\) が存在するならば、それは \(P\) 以下です。そこで、\(M=\lfloor\sqrt{P}\rfloor\) として、Baby step Giant step を適用することを考えます。
\(f(x)=Ax+B\) の逆関数は \(f^{-1}(x)=Cx+D\) の形で具体的に求めることができます。また、 \(O(M)\) 時間かけることで、\(f^M\) を \(f^M(x)=A'x+B'\) の形で具体的に求めることができます。よって、予め \(T,f^{-1}(T),f^{-1}(f^{-1}(T)),\ldots\) を \(M\) 個列挙しておき、\(S,f^M(S),f^M(f^M(S)),\ldots\) の順に、これらと一致するものがあるかどうかを調べることで、\(O(M\log{M})\)で(あるいはhash mapを用いてexpected \(O(M)\) で)この問題を解くことができます。
実装する際には、数列 \((X_i)\) の周期が \(M\) 未満であるために \(T,f^{-1}(T),f^{-1}(f^{-1}(T)),\ldots\) の中に値の重複が起こるケースの扱いについて注意してください。(そのようなケースはそもそも答えが \(M\) 以下なので、最初に愚直に調べてしまうのも解決策の1つです)

実装例(C++)
実装例(Python)

別解

\(A=1\) のとき答えを求めることは容易です。\(A\neq 1\) の場合を考えます。\(\alpha=\frac{B}{A-1}\) とし、\(Y_i=X_i+\alpha\) と定めると、\(Y_i=AY_{i-1}\) となり \(Y_i=Y_0 A^i\) が得られます。したがって、元の問題は離散対数問題に帰着され、Baby step Giant step などのアルゴリズムを用いて \(O(\sqrt{P}\log{P})\)で(あるいはhash mapを用いてexpected \(O(\sqrt{P})\) で)解くことができます。
この解法は en_translator さんによるものです。

Bonus: \(P\) が素数でない場合を \(O(\sqrt{P}\log{P})\) で解いてみましょう