[SDOI2013]随机数生成器

$$X_{i+1} \equiv a*X_{i}+b\ (mod\  p)$$

$$给出a,b,X_1,求满足X_{i} = t的最小i $$

这道题也是一道BSGS。

 不难推出

$$X_{i+1} +\frac{b}{a-1} \equiv a*(X_{i}+\frac{b}{a-1})\ (mod\ p)$$

$$X_{n} +\frac{b}{a-1} \equiv a^{n-1}*(X_1+\frac{b}{a-1})\ (mod\ p)$$

那么只要求满足

$$a^x \equiv \frac{(a-1)t+b}{(a-1)X_1+b}\ (mod\ p)$$

的最小x即可,这一步可以使用BSGS解决。这道题还有一些特判,比较繁。代码如下:

发表评论

电子邮件地址不会被公开。 必填项已用*标注