hdu 2521 反素数
题意：求区间[a,b]中约数最多的那个数，如果有多个，输出最小的。
思路：看起来好像和反素数没什么关系...只是打个约数个数的表...
但是实际上，所有的答案恰好都是反素数。。。
我们回顾反素数的定义：设f(x)为x的约数个数，那么如果f(n)>f(i) (0<i<n),n就被称为反素数.
换句话说，对于所有f(x)==k的x组成的集合，最小的那个x就是反素数。
需要注意的是，因数个数并不单调。。因此上面那句话并不准确。。。
举个例子，16虽然有5个因子，是第一个有5个因子的数，但是16不是反素数，因为比16小的12有6个因子。
那么这个东西有什么用呢。。。。
我们发现。。。反素数的分布很稀疏。。。因此。。。可以直接打表。。。
一张反素数的表(一共167个)：
{1,2,4,6,12,24,36,48,60,120,180,240,360,720,840,1260,1680,2520,5040,7560,10080,15120,20160,25200,27720,45360,50400,55440,83160,110880,166320,221760,277200,332640,498960,554400,665280,720720,1081080,1441440,2162160,2882880,3603600,4324320,6486480,7207200,8648640,10810800,14414400,17297280,21621600,32432400,36756720,43243200,61261200,73513440,110270160,122522400,147026880,183783600,245044800,294053760,367567200,551350800,698377680,735134400,1102701600,1396755360,2095133040,2205403200,2327925600,2793510720,3491888400,4655851200,5587021440,6983776800,10475665200,13967553600,20951330400,27935107200,41902660800,48886437600,64250746560,73329656400,80313433200,97772875200,128501493120,146659312800,160626866400,240940299600,293318625600,321253732800,481880599200,642507465600,963761198400,1124388064800,1606268664000,1686582097200,1927522396800,2248776129600,3212537328000,3373164194400,4497552259200,6746328388800,8995104518400,9316358251200,13492656777600,18632716502400,26985313555200,27949074753600,32607253879200,46581791256000,48910880818800,55898149507200,65214507758400,93163582512000,97821761637600,130429015516800,195643523275200,260858031033600,288807105787200,391287046550400,577614211574400,782574093100800,866421317361600,1010824870255200,1444035528936000,1516237305382800,1732842634723200,2021649740510400,2888071057872000,3032474610765600,4043299481020800,6064949221531200,8086598962041600,10108248702552000,12129898443062400,18194847664593600,20216497405104000,24259796886124800,30324746107656000,36389695329187200,48519593772249600,60649492215312000,72779390658374400,74801040398884800,106858629141264000,112201560598327200,149602080797769600,224403121196654400,299204161595539200,374005201994424000,448806242393308800,673209363589963200,748010403988848000,897612484786617600,1122015605983272000,1346418727179926400,1795224969573235200,2244031211966544000,2692837454359852800,3066842656354276800,4381203794791824000,4488062423933088000,6133685312708553600,8976124847866176000,9200527969062830400}
当然这道题数据小可以直接打因数个数的表...
1/* ***********************************************
2Author :111qqz
3Created Time :Wed 21 Sep 2016 04:00:39 PM CST
4File Name :code/hdu/2521.cpp
5************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#define fst first
19#define sec second
20#define lson l,m,rt<<1
21#define rson m+1,r,rt<<1|1
22#define ms(a,x) memset(a,x,sizeof(a))
23typedef long long LL;
24#define pi pair < int ,int >
25#define MP make_pair
26using namespace std;
27const double eps = 1E-8;
28const int dx4[4]={1,0,0,-1};
29const int dy4[4]={0,-1,1,0};
30const int inf = 0x3f3f3f3f;
31const int N=5005;
32int num[N];
33int factor( int n)
34{
35 if (n==1) return 1;
36 int res = 2 ;
37 int mx = n;
38 for ( int i = 2 ; i < mx ; i++)
39 if (n%i==0)
40 res = n/i==i?(res+1):(res+2),mx=n/i;
41 return res;
42}
43int main()
44{
45 #ifndef ONLINE_JUDGE
46 freopen("code/in.txt","r",stdin);
47 #endif
48 for ( int i = 1 ; i <= 5000 ; i++) num[i] = factor(i);
49 int T;
50 cin>>T;
51 while (T--)
52 {
53 int a,b;
54 scanf("%d%d",&a,&b);
55 int ans;
56 int mx = -1;
57 for ( int i = a; i <= b ; i++)
58 {
59 if (num[i]>mx)
60 {
61 mx = num[i] ;
62 ans = i;
63 }
64 }
65 printf("%d\n",ans);
66 }
67 #ifndef ONLINE_JUDGE
68 fclose(stdin);
69 #endif
70 return 0;
71}