「SDOI2013」随机数生成器-BSGS

发布于 13 天前  31 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:「SDOI2013」随机数生成器-BSGS

Description

给定随机生成数种子 \(x_1,a,b\),\(x_i=ax_{i-1}+b(mod P)\),求最小的\(i\)使得\(x_i=t\)。

\(P \leq 10^9\)

Solution

\(a^{i-1}x_1+a^{i-2}b+a^{i-3}b+...+b\equiv t(mod p)\)

等价与

\(a^{i+1}x_1+a^{i}b+a^{i-1}b+...+b\equiv t(mod p)\)

\(a^{i+1}x_1+b \frac{a^{i+1}-1}{a-1}\equiv t(mod p)\)

\(a^{i+1}\equiv \frac{t(a-1)+b}{x_1\times a - x_1+b}(mod p)\)

BSGS即可。

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:「SDOI2013」随机数生成器-BSGS


或许前方只有...伸手不见五指的夜路,即使如此,我还是要充满信心、继续向前,相信星星的光芒...多少会照亮前方的道路,走吧!我们踏上旅程吧!