POJ3292/UVA11105 H-半素数 Semi-prime H-numbers

Luogu RemoteJudge

POJ-Vjudge

UVA-Vjugde

题意

给你一个由 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+=i4

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;
}