当前位置:首页 >> 其它课程 >> hdu hdoj 1406 完数

hdu hdoj 1406 完数


一、 问题描述

完数
Time Limit: 2000/1000 MS (Java/Others) Total Submission(s): 9129 Memory Limit: 65536/32768 K (Java/Others) Accepted Submission(s): 3047

Problem Descripti

on
完数的定义:如果一个大于 1 的正整数的所有因子之和等于它的本身,则称这个数是完数, 比如 6,28 都是完数:6=1+2+3;28=1+2+4+7+14。 本题的任务是判断两个正整数之间完数的个数。

Input
输入数据包含多行, 第一行是一个正整数 n, 表示测试实例的个数, 然后就是 n 个测试实例, 每个实例占一行,由两个正整数 num1 和 num2 组成,(1<num1,num2<10000) 。

Output
对于每组测试数据,请输出 num1 和 num2 之间(包括 num1 和 num2)存在的完数个数。

Sample Input
2 2 5 5 7

Sample Output
0 1

Author
lcy

Source
杭电 ACM 集训队训练赛(IV)

Recommend
Ignatius.L

二、 问题分析与算法实现 三、 参考代码
#include <iostream> #include <cmath> #define MAX 10000 using namespace std; int i,j; int len=0; int Prime[MAX/3],NotPrime[MAX]; void GetPrime() { for(i=2;i<MAX;i++) { if(NotPrime[i]==0) { Prime[len++]=i; } for(j=0;j<len&&Prime[j]*i<MAX;j++) { NotPrime[Prime[j]*i]=1; if(i%Prime[j]==0) break; } } } int Perfect[MAX+1]; void GetPerfectNumber() { int i,sum; int a,m; int N; GetPrime(); for (i=2;i<10001;i++) { m=0; sum=1; N=i;

while(N>1) { a=0; while(N%Prime[m]==0) { N/=Prime [m]; a++; } if(a>0) { sum=sum*(pow(Prime[m],(a+1))-1)/(Prime[m]1); } m++; } Perfect[i]=Perfect[i-1]; if(sum==2*i) { Perfect[i]++; } } } int main() { int n; int a,b,temp; GetPerfectNumber(); cin>>n; while(n--) { cin>>a>>b; if(a>b) { temp=a; a=b; b=temp; } cout<<Perfect[b]-Perfect[a-1]<<endl; } return 0; }

#pragma warning (disable:4786) #include <iostream> #include <set> using namespace std; //求 330 以内的所有素数 int len; const int MAX=330; bool Notprime[MAX]; int prime[MAX/3]; void get_prime() { len=0; int i,j; for(i=2;i<MAX;i++) { if(!Notprime[i]) prime[len++]=i; for(j=0;i*prime[j]<=MAX && j<len;j++) { Notprime[i*prime[j]]=true; if(i%prime[j]==0) break; } } }

int perfect[10000]; set<int> s; set<int>::iterator it;

//2 到 n 时共有的 perfect 数

//插入因子 n,如已有 1,3,5,插入因子 2 后变成 1,3,5,6,10 void my_insert(int n) { it=s.end (); it--;

for(;it!=s.begin();it--) { s.insert (n*(*it)); } s.insert (n*(*it)); } //完数返回 1,否则返回 0 int Isperfect(int n) { int temp; int i; temp=n; s.clear (); s.insert (1); i=0; while(temp!=1 && i<len) { if(temp%prime[i]==0) { temp=temp/prime[i]; my_insert(prime[i]); } else i++; } //temp 本身是一个大的素数时 if(temp>1) my_insert(temp); temp=0; for(it=s.begin ();it!=s.end ();it++) temp+=(*it); //因为多插入了一个 n if(temp==2*n) return 1; else return 0; }

//获得完数个数 void get_perfect_num() { int i; perfect[1]=0; for(i=2;i<10000;i++) { perfect[i]=perfect[i-1]+Isperfect(i); } } int main() { int temp; int n,m; int t; get_prime(); // for(i=0;i<len;i++) // cout<<prime[i]<<" "; get_perfect_num(); cin>>t; while(t--) { cin>>n>>m; if(n>m) { temp=n; n=m; m=temp; } cout<<perfect[m]-perfect[n-1]<<endl; } return 0; }

蔡尚真 代码;阮凯云 2011-10-25 整理


更多相关文档:

hdu hdoj 1406 完数

hdu hdoj 1406 完数_其它课程_高中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 hdu hdoj 1406 完数_其它课程_高中教育_教育专区。一、 问题描述 完数 ...

hdu hdoj 1215 七夕节

hdu hdoj 1406 完数 暂无评价 6页 1下载券 hdu hdoj 1174 爆头 3页 1下载券 hdu hdoj 1106 排序 暂无评价 3页 1下载券 hdu hdoj 1412 {A} + {B......

hdu hdoj 1140 War on Weather

hdu hdoj 1406 完数 暂无评价 6页 2财富值 hdu hdoj 1174 爆头 3页 2财富值 hdu hdoj 1106 排序 暂无评价 3页 2财富值 hdu hdoj 1412 {A} + {B} 暂...

hdu hdoj 1236 排名

hdu hdoj 1406 完数 暂无评价 6页 1下载券 hdu hdoj 1174 爆头 3页 1下载券 hdu hdoj 1106 排序 暂无评价 3页 1下载券 hdu hdoj 1412 {A} + {B......

hdu hdoj 1521 排列组合

hdu hdoj 1406 完数 暂无评价 6页 2财富值 hdu hdoj 1174 爆头 3页 2财富值 hdu hdoj 1106 排序 暂无评价 3页 2财富值 hdu hdoj 1412 {A} + {B} 暂...

hdu hdoj 1174 爆头

hdu hdoj 1406 完数 暂无评价 6页 2财富值 hdu hdoj 1106 排序 暂无评价 3页 2财富值 hdu hdoj 1412 {A} + {B} 暂无评价 3页 2财富值 hdu hdoj 1236...

hdu hdoj 1233 还是畅通工程

hdu1233 暂无评价 1页 免费 hdu hdoj 1406 完数 暂无评价 6页 1下载券 hdu hdoj 1174 爆头 3页 1下载券 hdu hdoj 1106 排序 暂无评价 3页 1下载券 hdu ...

hdu hdoj 1412 {A} + {B}

hdu hdoj 1412 {A} + {B}_英语学习_外语学习_教育专区。一、 问题描述 {...hdu hdoj 1262 寻找素数... hdu hdoj 1286 找新朋友 hdu hdoj 1406 完数1...

杭电ACM部分题目答案

("%d\n",k); } } 2033 人见人爱 A+B Problem Description HDOJ 上面已经有 10 来道 A+B 的题目了,相信这些题目曾经是大家的最爱,希望今天的这 个 A...

hdu_hdoj_1106_排序

hdu_hdoj_1106_排序_计算机软件及应用_IT/计算机_专业资料。一、 问题描述 排序 Time Limit: 2000/1000 MS (Java/Others) Total Submission(s): 16817 Memory...
更多相关标签:
hdu 1406 | hdoj题目分类 | hdoj 1532 | hdoj1002 | hdoj2000 | hdoj1003 | hdoj1001 | hdoj1005 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com