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()给运行错误了一天，晚上发现错误了算法又出了问题。哎哎，不行呀。周末的华为，赶紧的，刷几个题再说！！！
压力山大哈！呵呵，心态最重要，没事没事，开朗豁达就行。