题面

题面链接

题目大意

形如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合成数”了吗？

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

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

是4n+1的倍数
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合成数

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1000004;
bool p[MAXN];
int prime[MAXN],cnt;
int s[MAXN];
int n;

void primes(int n){
    for(int i=5;i<=n;i+=4){
        if(p[i])continue;
        prime[++cnt]=i;
        for(int k=1;k*i<=n;k+=4){
            p[k*i]=1;
        }
    }
}

int main(){
    primes(1000001);
    for(int i=1;i<=cnt;i++){
        for(int j=1;j<=i&&prime[i]*prime[j]<MAXN;j++){
            s[prime[i]*prime[j]]=1;
        }
    }
    for(int i=1;i<=1000001;i++)s[i]+=s[i-1];
    while(scanf("%d",&n)){
        if(n==0)break;
        printf("%d %d\n",n,s[n]);
    }
    return 0;
}

#include<bits/stdc++.h>

using namespace std;

const int MAXN=1000004;

bool p[MAXN];

int prime[MAXN],cnt;

int s[MAXN];

int n;

void primes(int n){

for(int i=5;i<=n;i+=4){

if(p[i])continue;

prime[++cnt]=i;

for(int k=1;k*i<=n;k+=4){

p[k*i]=1;

}

int main(){

primes(1000001);

for(int i=1;i<=cnt;i++){

for(int j=1;j<=i&&prime[i]*prime[j]<MAXN;j++){

s[prime[i]*prime[j]]=1;

}

for(int i=1;i<=1000001;i++)s[i]+=s[i-1];

while(scanf("%d",&n)){

if(n==0)break;

printf("%d %d\n",n,s[n]);

}

return 0;

}

发送评论编辑评论

题面

题目大意

题解

发送评论 编辑评论

发送评论编辑评论