一道水题 LOJ6165 线性筛(含线性筛学习笔记)

传送门:https://loj.ac/problem/6165
这题“一道水题”,一道非常难的数学题。(主要是我不会线性筛)
先来讲一下线性筛(欧拉筛法):
我们从2一直找到\(n\),如果这个数没有被标记为非质数,就把它放进一个记录目前找到的所有质数的数组\(prime\)里面,并且用\(pri\)这个数记录下当前有多少个质数。
然后我们把从\(prime[1]\)到\(prime[pri]\)和当前的数\(i\)的乘积标记为非质数,如果乘积超过\(n\)就结束循环。
慢着,这不是和普通筛法一样?关键的来了!!!
这是线性筛中非常关键的一行代码:

正是它,使得这种筛法变为线性的。
因为如果\(i\)是\(prime[j]\)的倍数,那么之前在删\(prime[j]\)和别的数的乘积的时候肯定已经把\(i\)的倍数删掉了。如果不好理解,可以自己模拟一下。
这样,每个合数都会被删掉,并且不会被重复删掉。这使得它的复杂度成为线性的了。
普通筛法——埃拉托斯特尼筛法的时间复杂度为\(O(n\ log\ log\ n)\),空间复杂度为\(O(n)\)。如果数据中\(n\)达到了\(10^8\)(比如现在讲的这题),那么就会超时。
这种筛法——欧拉筛法的时间复杂的为\(O(n)\)。
讲完线性筛,再来讲讲这题的做法。
这题是要求\([1,n]\)中所有数的最小公倍数模\(10^8+7\)的值,其实也就是求每一个数分解质因数后,把所有质数的次数取最高次然后乘起来。例如题目样例,\(1\sim 10\)中,2的最高次是3(\(8=2^3\)),3的最高次是2(\(9=3^2\)),5的最高次是1,7的最高次也是1,那么最终的答案为\(2^3\times 3^2\times 5\times 7=2520\)。
我们在筛每一个质数\(i\)的之前,就可以先计算出它的最高次应该是多少(即使得\(i^t\leq n\)的最大的\(t\)),然后把它乘进\(ans\)中并对\(10^8+7\)取模即可(初始化\(ans=1\))。
这样做时间复杂度当然是\(O(n)\)的,但是由于有常数,并且时间限制只有\(1s\),我们还需要进行常数上的优化。由于空间限制只有\(128MB\),我们一定要注意空间问题。(我也不知道我是怎么把它优化到时空限制都符合要求的,反正我的原则是:能不开long long就不开long long,能不把变量开在循环里面就不把变量开在循环里面。再加上可能LOJ评测机的速度比较可观,就愉快地AC啦~)其实我优化了好久的QAQ。。。
AC代码:

 

发表评论