数论吧 关注:13,458贴子:75,812
  • 7回复贴,共1

已知线性同余发生器的a、c、m、x0,问如何快速的求得x8888888888

只看楼主收藏回复

普通的线性同余发生器,不考虑极简单的情况,即a!=0,a!=1,c!=0,m!=2的幂,x0!=0。
比如,a=354364375;c=4325426;m=465433725(随手敲的),x0=1。
如果不采用叠代公式xn=a*x(n-1)+c || m,有没有加速算法?比如能在1000步以内得到x1000000000,x10000000000000000等数?


1楼2021-07-17 00:53回复
    可以先算一下周期,会不会方便一点,
    还有为什么2的幂次和x0=0是简单情形啊(●—●),x0=0好像也很难算


    IP属地:安徽来自Android客户端2楼2021-07-17 07:09
    收起回复
      回楼上的,我又想了一下,通常的m都是上百位(我出的题目中m有点小),就算知道了周期也没有办法加速……


      3楼2021-07-17 08:18
      收起回复