首页 > ACM题库 > HDU-杭电 > hdu 2521 反素数-数论-[解题报告]C++
2014
02-09

hdu 2521 反素数-数论-[解题报告]C++

反素数

问题描述 :

反素数就是满足对于任意i(0<i<x),都有g(i)<g(x),(g(x)是x的因子个数),则x为一个反素数。现在给你一个整数区间[a,b],请你求出该区间的x使g(x)最大。

输入:

第一行输入n,接下来n行测试数据
输入包括a,b, 1<=a<=b<=5000,表示闭区间[a,b].

输出:

第一行输入n,接下来n行测试数据
输入包括a,b, 1<=a<=b<=5000,表示闭区间[a,b].

样例输入:

3
2 3
1 10
47 359

样例输出:

2
6
240
Hint
2的因子为:1 2 10的因子为:1 2 5 10

解题报告:水题,直接附上代码,只是觉得这题的作者是不是吃饱了饭撑的,反素数的概念跟这题一点关系都没有。

#include<cstdio>
 int judge1(int k) {
     int tot = 0;
     for(int i = 1;i<=k;++i)
     if(!(k%i))
     tot++;
     return tot;
 }
 int main( ) {
     int n,a,b;
     scanf("%d",&n);
     while(n--) {
         scanf("%d%d",&a,&b);
         int MIN = a;
         for(int i = a;i<=b;++i)
         if(judge1(i)>judge1(MIN))
         MIN = i;
         printf("%d\n",MIN);
     }
     return 0;
 }

 

解题转自:http://www.cnblogs.com/xiaxiaosheng/archive/2013/07/19/3200949.html


  1. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。