题意
给你一个由 4n+1 的数组成的集合,该集合中的数被称为 H 数,集合中的素数是 H- 素数, 两个 H- 素数的乘积组成的数被称为H- 合成数,现在给定一些 h ,求 [0,h] 中的 H- 合成数的个数。
题解
在数学一本通里面看到的这题,觉得那个写的太差了啥都没看懂,决定写一发题解。(就是自己太菜了
首先可以想到最朴素的做法就是直接预处理一个 [1,10^6] 的质数表,然后爆找既是两个质数的乘积又满足是 4n+1 组成的数,然后处理一个前缀和。
据说这样是可以过的,但是我也不知道。
可以优化的地方就在找质数这个地方。考虑埃氏筛的过程,我们可以把每次枚举的数改一改,从i++
变为i+=4
,这样我们每次就枚举的都是 H 数。
据说这样也是可以过的,但是我还是不知道。
引理:若 i 是一个 H- 素数,则 5i + 4i * x 是 H 数但不是H- 素数
证明:设 i = 4p+1
由原式可得:(5(4p+1) + 4(4p+1)*x) \ mod\ 4= 1
观察后面 $4(4p+1)x\ mod\ 4 = 1,由同余性质可得:(4(4p+1)\ mod \ 4) (x\ mod\ 4)\ mod\ 4 = 1$
显然:4(4p+1)\ mod \ 4 必然等于 1 ,根据算术结果,可知 x\ mod \ 4 = 1
将$(5(4p+1) + 4(4p+1)x) \ mod\ 4= 1拆开得到:(20p+5+x(16p+4))\ mod\ 4 = 1, 可知5i + 4i x是H$ 数。
又因为$5i + 4i x可以写成:i(4x+5),所以5i + 4i x不是H-$ 素数。
证毕。
所以可以再次修改埃氏筛除合数的过程,将范围修改为:$[i5, 10^6]$ ,并将每次找的数从j++
修改为j+=i
4
Code
#include <iostream>
#include <cstdio>
using namespace std;
const int SIZE = 1e6 + 5;
int h, cnt;
int h_prime[SIZE], h_semi[SIZE], vis[SIZE], sum[SIZE];
inline int read()
{
char ch = getchar();
int f = 1, x = 0;
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
return x * f;
}
inline void init()
{
for (int i = 5; i <= SIZE - 5; i += 4) {
if (vis[i]) continue;
h_prime[++cnt] = i;
for (int j = i * 5; j < SIZE; j += i * 4) vis[j] = 1;
}
for (int i = 1; i <= cnt; i++)
for (int j = 1; j <= i && h_prime[i] * h_prime[j] < SIZE; j++) h_semi[h_prime[i] * h_prime[j]] = 1;
for (int i = 1; i < SIZE; i++) sum[i] = sum[i - 1] + h_semi[i];
}
int main()
{
init();
h = read();
while (h) {
printf("%d %d\n", h, sum[h]);
h = read();
}
return 0;
}
Comments | NOTHING