当前位置:首页 >> 其它课程 >> 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 Description
完数的定义:如果一个大于 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 1521 排列组合

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 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 1233 还是畅通工程

hdu hdoj 1251 统计难题 hdu hdoj 1262 寻找素数... hdu hdoj 1286 找新朋友 hdu hdoj 1406 完数 hdu hdoj 1412 {A} + {B... 1/2 相关文档推荐 hdu12...

Hdu中文题目

Hdu中文题目_IT认证_资格考试/认证_教育专区。HDU里边的中文题目你HDOJ 中文题目(第 1 部分) Start Time : 2013-11-07 11:07:00 End Time : 2013-12-04 ...

hdu hdoj 1212 Big Number

hdu hdoj 1212 Big Number_英语学习_外语学习_教育专区。一、 问题描述 Big Number...hdu hdoj 1406 完数 hdu hdoj 1412 {A} + {B... hdu hdoj 1521 排列...

hdu hdoj 1106 排序

hdu hdoj 1106 排序_计算机软件及应用_IT/计算机_专业资料。一、 问题描述 排序 Time Limit: 2000/1000 MS (Java/Others) Total Submission(s): 16817 Memory...

hdu_hdoj_1106_排序

hdu_hdoj_1106_排序_计算机软件及应用_IT/计算机_专业资料。一、 问题描述 排序 Time Limit: 2000/1000 MS (Java/Others) Total Submission(s): 16817 Memory...

hdu hdoj 1237 简单计算器

hdu hdoj 1406 完数 暂无评价 6页 2财富值 hdu hdoj 1174 爆头 3页 2财富...hdu hdoj 1237 简单计算器 隐藏>> 一、 问题描述 简单计算器 Time Limit: 2000...

hdu hdoj 1286 找新朋友

hdu hdoj 1286 找新朋友_数学_自然科学_专业资料。一、 问题描述 找新朋友 Time...hdu hdoj 1406 完数 hdu hdoj 1412 {A} + {B... hdu hdoj 1521 排列组...
更多相关标签:
网站地图

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