poj 3243 hdu 2815 baby_step gaint_step 算法
2009-10-01 20:53
baby_step gaint_step 算法基本思想:
對于一個n個元素的循環(huán)(n很大很大) 先算出前面m步(baby_step) 然后以m為跨度(gaint_step)大跳 那么跳了n/m步以后 一定能跳到前面算出來的m步里面 這樣時間復(fù)雜度就降到O(m+n/m) 空間復(fù)雜度為O(m)
對于計算a^x==b(mod n)中的x
先計算b,b*a,b*a^2,...b*a^m 然后計算1，a^m,a^2m,a^3m,... 那么經(jīng)過i步 就是到了a^(i*m)的時候 發(fā)現(xiàn)它等于b*a^j 那么x=i*m-j
一般m定為sqrt(n)平衡時空(并且這樣時間復(fù)雜度最低） 查找用hash 事實證明map是非常慢的
//更新
經(jīng)過AekdyCoin蓋世神牛的檢驗 我那個能在poj上跑的程序在hdu上先MLE 然后TLE 然后CE 然后RE 然后WA 千辛萬苦 最后跳過PE 變成AC了
原因:動態(tài)鏈表hash跑太慢 以后要改成前向星了
//繼續(xù)更新
經(jīng)過AekdyCoin教導(dǎo) 發(fā)現(xiàn)這個算法當(dāng)a和n不互質(zhì)的時候會死 因為沒有逆元 i*m-j不能隨便減
于是連夜開發(fā)不互質(zhì)算法如下
設(shè)某質(zhì)數(shù)p在a里的指數(shù)是ap 在n里面是np 在b里面是bp
那么當(dāng)x很大 ap*x必然大于np 這個時候bp必須不小于np 其逆命題也成立
同時 將n里面的p全部除掉 剩下的由于和p互質(zhì) 所以左邊a，b可不必除 反正最后a^x-b一定整除n
所以 先判斷a和n的公共質(zhì)因數(shù)里面 有沒有b比n小的 若小必死 否則直接將n除的和a互質(zhì)再做完破
注意到每個質(zhì)數(shù)的指數(shù)肯定不超過40 那么當(dāng)x大于40以上方法必然成立 當(dāng)x小的時候 雖然經(jīng)證明也可以化為abn互質(zhì)情況 但是不如直接驗證 所以不管了
寫了一天了，先是被qsort()寫成qsrot()給運行錯誤了一天，晚上發(fā)現(xiàn)錯誤了算法又出了問題。哎哎，不行呀。周末的華為，趕緊的，刷幾個題再說！！！
壓力山大哈！呵呵，心態(tài)最重要，沒事沒事，開朗豁達就行。