好消息,我发题了!链接(在团队里,团队外打不开)
first,我要令 n=r−ln=r-ln=r−l.
首先我们看到数据范围这么大,用普通的判断质数肯定是行不通的
时间复杂度:O(nr)O(n\sqrt r)O(nr ),放在这个的数据直接被硬控 NaNNaNNaN 秒.
但是用筛的话,n≤2×109n\le2\times10^9n≤2×109 任何线性筛都会爆炸
这时候,不得不放出我O(nlogn)O(\dfrac{n}{\log n})O(lognn )的筛法了(
算了还是不展示了(
正经点,我们可以改进埃式筛
普通埃式筛是筛掉 nnn 以内所有的数,但现在我们只要范围内的数就行了,所以我们可以转找范围内的数筛
时间复杂度:O(nlogr)O(n\log r)O(nlogr)(蒙的).
这个已经可以过了,但是还能不能再快点呢?
时间复杂度:O(nloglogr)O(n\log\log r)O(nloglogr)(也是蒙的).
反正更快就行了