首页 > ACM题库 > HDU-杭电 > HDU 1406 完数[解题报告] C++
2013
12-09

HDU 1406 完数[解题报告] C++

完数

问题描述 :

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

本题的任务是判断两个正整数之间完数的个数。

输入:

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

输出:

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

样例输入:

2
2 5
5 7

样例输出:

0
1

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 10010
int a[N];
int flag[N];
void Fuck()
{
    memset(a,0,sizeof(a));
    memset(flag,0,sizeof(flag));
    for(int i=1;i<=N;i++)
    for(int j=2*i;j<=N;j+=i)
    a[j]+=i;
    for(int i=1;i<=N;i++)
    if(a[i]==i)
    flag[i]=1;
}
int main()
{
    int t;
    scanf("%d",&t);
    Fuck();
    while(t--)
    {
        int x,y;
        int count=0;
        scanf("%d%d",&x,&y);
        if(x>y)
        swap(x,y);
        for(int i=x;i<=y;i++)
        if(flag[i])
        count++;
        printf("%d\n",count);
    }
    return 0;
}

解题报告转自:http://blog.csdn.net/shiyuankongbu/article/details/7970615


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。

  3. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.