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