poj 3243 hdu 2815 baby_step gaint_step 算法
2009-10-01 20:53
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互質情況 但是不如直接驗證 所以不管了
寫了一天了，先是被qsort()寫成qsrot()給運行錯誤了一天，晚上發現錯誤了算法又出了問題。哎哎，不行呀。周末的華為，趕緊的，刷幾個題再說！！！
壓力山大哈！呵呵，心態最重要，沒事沒事，開朗豁達就行。