首页 > 代码库 > POJ3292 Semi-prime H-numbers
POJ3292 Semi-prime H-numbers
传送门：
刷《数论一本通》时看到的题，简单记录一下。
题目大意（照抄书上的）：形如4n＋1的数被称为H数，乘法在H数组成的集合内是封闭的。在这个集合中是能被1和本身整除的数叫H－素数，其余的数被称为H合数，1个
H－合成数是一个能且只能被分解成两个H－素数乘积的H合数，求0-h内有多少个H合成数。
题解：
首先，两个H素数的乘积一定是H数，这个可以推导出来：
所以只要我们求出0-h内有多少个H素数，就可以得到本题的答案。根据同余原理我们知道如果i是素数，那么i（5+4x）必定不是H素数且一定是H数，那么就可以通过筛发求出本题的答案。
1 //POJ 3292 2 //by Cydiater 3 //2016.8.29 4 #include <iostream> 5 #include <cstdio> 6 #include <cstdlib> 7 #include <cstring> 8 #include <string> 9 #include <iomanip>10 #include <ctime>11 #include <cmath>12 #include <queue>13 #include <map>14 #include <algorithm>15 using namespace std;16 #define ll long long17 #define up(i,j,n) for(int i=j;i<=n;i++)18 #define down(i,j,n) for(int i=j;i>=n;i--)19 const int MAXN=1e6+5;20 const int LIM=1e6+1;21 const int oo=0x3f3f3f3f;22 inline int read(){23 char ch=getchar();int x=0,f=1;24 while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}25 while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}26 return x*f;27 }28 int prime[MAXN],semi[MAXN],ans[MAXN],Count[MAXN],cnt=0,N;29 namespace solution{30 void pret(){31 memset(prime,0,sizeof(prime));32 memset(semi,0,sizeof(semi));33 memset(ans,0,sizeof(ans));34 for(int i=5;i<=LIM;i+=4){35 if(prime[i])continue;36 Count[++cnt]=i;37 for(int j=0;i*(4*j+5)<=LIM;j++)prime[i*(4*j+5)]=1;38 }39 up(i,1,cnt)up(j,1,i)if(Count[i]*Count[j]>LIM)break;40 else semi[Count[i]*Count[j]]=1;41 up(i,1,LIM)ans[i]=ans[i-1]+semi[i];42 }43 void slove(){44 while(scanf("%d",&N)&&N!=0)printf("%d %d\n",N,ans[N]);45 }46 }47 int main(){48 //freopen("input.in","r",stdin);49 using namespace solution;50 pret();51 slove();52 return 0;53 }
POJ3292 Semi-prime H-numbers
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。