这一题的主要思路是不用把1-n全部都刷一遍,将m个数的所有倍数都找出来,然后用容斥原理整合一下就行了。
难点完全不在前四十分钟的公式和证明,难点在正好有m个质数,这些数的容斥原理展开的多项式之和正好有2^m - 1个,正好可以用2^m个数的二进制来表示m个质数哪些取到了哪些没有取到,正好这样的位运算这样写巨nm方便。然后这样写的边界条件又特别容易通过性质理解和记忆。
然后这一切都在y总的谈笑风生之间几十秒钟就敲完了,刷这一道题真的算是一种修行, 把容易想到但是又要注意到的细节都自己过一遍。