题解 P2429 【制杖题】

war1111 · 2017-10-20 11:45:06 · 题解

对线性筛的新理解

除了最小质数的原因外，还有一方面，就是当前的枚举的倍数一定比筛出来的质数小，这是排除了哪种情况呢？

倍数 质数

2 13

倍数 质数

13 2

这个题用线性筛会WA一个点，因为这个题是给定的质数集，最大的质数会比当前的倍数大，就会出现上面的情况。

怎办？

判重用set啊！

set+线性筛就过掉了。16ms

标程在blog里。

http://www.cnblogs.com/war1111/p/7698718.html