[BZOJ3122] [SDOI2013] 随机数生成器

题目

题目链接
题目大意为从第一天开始看书为 x_1 页, x_n 满足 x_{i+1} = ax_i+b\ mod\ p, 求第几天可以看到 t 页。
 

思路

首先进行分类讨论,为了方便,将第一天就在 t 页的处理,即 t == x_1 的情况。然后分 3 类。
第一类 a == 0
则只需判断 b == t, 如果相等,则第二天就能看见,否则看不见。
第二类 a == 1
式子则可化简为 x_n = x_1 + (n-1)b, 则有 (n-1)b \equiv t - x_1\ (Mod\ p). 这样用扩展欧几里得便可求出 (n-1), 无解的情况即为扩展欧几里得无解的情况。
第三类 a == 1
式子两边补项化简可得 x_{i+1} + bc = a(x_i + bc) 其中 c \equiv (a-1)^{-1}\ (Mod\ q).接着化简得 x_{n} + bc = (x_1 + bc)a^{n-1} 带入 t 则有 a^{n-1}(x_1 + bc)\equiv t + bc\ (Mod\ q) 接着可用扩展欧几里得求出 a^{n-1}, 接着就可以用 BSGS 算法求出 n 了。如果扩展欧几里得或者 BGSG 无解,则此题无解。
 

代码

 

完结

参考了 黄学长博客
以后还是不可以偷懒将变量名取作 xx, xxx, yy 了,因为把 xx 写成了 x, debug 了一下午😑😑😑😑😑,长记性了。

发表评论

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