[UVA11105] Semi-prime H-numbers

题面

题面链接

题目大意

形如4n+1的数被称为“H数”,乘法在“H数”组成的集合内是封闭的。在这个集合中只能被1和本身整除的数叫做“H素数”(不包括1),其余的数被称为“H合数”。一个“H合成数”是一个能且只能分解成两个“H素数”乘积的“H合数”(可能由多种分解方案)。比如441=2121=949,所以411是“H合成数”,125=555,所以125不是“H合成数”。
求0~h范围内“H合成数”的个数。

题解

思路其实很简单,既然只有两个“H素数”的乘积是一个“H合成数”的话,那么我们把所有的“H素数”筛出来再来组合不就是“H合成数”了吗?

筛法我们可以直接在埃式筛法上改一下,也就是标记合数的方法。

也就是我们要标记的数其实是满足:

  1. 是4n+1的倍数
  2. mod4余1

于是我们可以得到下面的式子:


\(k(4n+1)\%4=1\)

\(4kn\%4+k\%4=1\)

\(k\%4=1\)


就可以得到k其实是下面这组数:

\(\{k|k\in 4i+1,i\ge1\}\)

筛出H素数后枚举两两相乘(超过了1000001就break啦,不要再作没意义的事),开个桶s(0和1,顺便起到去重的作用),然后算桶的前缀和,s[i]就是0~i范围内的H合成数

发表评论

电子邮件地址不会被公开。 必填项已用*标注