「Luogu3306」[SDOI2013]随机数生成器

Solution

我们来回忆一下数列递推公式求通项的方法

令\(Y_i=X_i+\frac{b}{a-1}\)，则有

\[Y_i=aY_{i-1}\Rightarrow Y_i=a^{i-1}Y_1\]

于是题目转化为求解方程

\[t+\frac b{a-1}\equiv a^{x-1}(X_1+\frac b{a-1})\pmod p\]

\[\Rightarrow a^{x-1}\equiv\frac{t+\frac b{a-1}}{X_1+\frac b{a-1}}\pmod p\]

好的，这个东西我们只要用BSGS就可以了

End?

---

几个细节：

\(X_1=t\)时，直接输出\(1\)

当\(a=0\)时，输出若\(b=t\)则输出\(2\)，否则无解，\(X_1=t\)的情况已经特判

当\(a=1\)时，方程实际上为

\[(x-1)b\equiv t-X_1\pmod p\]

根据裴蜀定理判掉无解，然后直接算\(x-1\)即可

需要注意的是如果\(\frac{t-X_1} b=p\)，则不需要取模直接输出

True End

Code

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include