当前位置:www.lilai99.com > 振动筛原理 > 正文

线性筛(欧拉筛)

  昨天的考试跪的一塌糊涂:第一题水过,第二题带WA的朴素,最后题忘了特判左端点全跪,分数比起预计得分整整打了个对折啊!

  一般的筛法(PPT里叫埃拉托斯特尼筛法,名字异常高贵)的效率是O(NlglgN)(其实很接近O(n)啊!),对于一些例如N=10000000的残暴数据会跪,于是,线性筛登场了

  1.两层循环的顺序不同(一般筛是第一维prime[i] 第二维j,欧拉筛是第一维i 第二位prime[j])

  这行代码神奇地保证了每个合数只会被它的最小素因子筛掉,就把复杂度降到了O(N)。

  P.S.因为自己很蠢,从下午开始研究,吃完饭之后看了部电影,百度了下,找到一个讲的超好的网站,它的说法如下:

  显然,线性筛只拿来筛筛素数是很不科学的,它的速度大约是一般筛的3~4倍,在数据量小的时候甚至慢些(用到了mod运算)。环亚游戏

  积性函数f(x)应满足f(a×b)=f(a)×f(b),a与b应互素。而完全积性函数则应满足对于任意的a与b,前面的等式应成立。

  原因1保证了每个数的phi只会被计算一次,第10行的代码可以由原因2解释,第20行的代码可以由原因2与原因3解释,第17行的代码可以由原因5所解释。

  记每个数因数个数为e(i),显然函数e(i)是积性函数但不是完全积性函数。

  对于i与prime[j]互素的情况,直接相乘即可。而对于i与prime[j]不互素的情况,就有点复杂了。

  我们要再记录一个num数组,num[i]表示i的最小素因子(即每次递推时的prime[j])的次数。

  显然,函数q是积性的,我们只用考虑i与prime[j]不互质的情况,一种办法是用乘法逆元搞,显然这是不科学的,真正的做法如下

  其中的prime[j]num[i]是可以预先存好的。这种做法还是利用了积性函数的性质。

上一篇:九龙电液动三通分料器咨询-扬州聚宇机械   下一篇:凡是机械的运动部件
用户名: 新注册) 密码: 匿名评论
评论内容:(不能超过250字,需审核后才会公布,请自觉遵守互联网相关政策法规。)
热门搜索:

线性筛(欧拉筛)

昨天的考试跪的一塌糊涂:第一题水过,第二题带WA的朴素,最后题忘了特判左端点全跪,分数比起预计得分整整打了个对折啊! 一般的筛法(PPT里叫埃拉托斯特尼筛法,名字异常高贵