baby_step gaint_step 算法基本思想:

對于一個n個元素的循環(n很大很大) 先算出前面m步(baby_step) 然后以m為跨度(gaint_step)大跳 那么跳了n/m步以后 一定能跳到前面算出來的m步里面 這樣時間復雜度就降到O(m+n/m) 空間復雜度為O(m)

對于計算a^x==b(mod n)中的x

先計算b,b*a,b*a^2,...b*a^m 然后計算1，a^m,a^2m,a^3m,... 那么經過i步 就是到了a^(i*m)的時候 發現它等于b*a^j 那么x=i*m-j

一般m定為sqrt(n)平衡時空(并且這樣時間復雜度最低） 查找用hash 事實證明map是非常慢的

//更新

經過AekdyCoin蓋世神牛的檢驗 我那個能在poj上跑的程序在hdu上先MLE 然后TLE 然后CE 然后RE 然后WA 千辛萬苦 最后跳過PE 變成AC了

原因:動態鏈表hash跑太慢 以后要改成前向星了

//繼續更新

經過AekdyCoin教導 發現這個算法當a和n不互質的時候會死 因為沒有逆元 i*m-j不能隨便減

于是連夜開發不互質算法如下

設某質數p在a里的指數是ap 在n里面是np 在b里面是bp

那么當x很大 ap*x必然大于np 這個時候bp必須不小于np 其逆命題也成立

同時 將n里面的p全部除掉 剩下的由于和p互質 所以左邊a，b可不必除 反正最后a^x-b一定整除n

所以 先判斷a和n的公共質因數里面 有沒有b比n小的 若小必死 否則直接將n除的和a互質再做完破

注意到每個質數的指數肯定不超過40 那么當x大于40以上方法必然成立 當x小的時候 雖然經證明也可以化為abn互質情況 但是不如直接驗證 所以不管了