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}
当然这道题数据小可以直接打因数个数的表...
/* ***********************************************
Author :111qqz
Created Time :Wed 21 Sep 2016 04:00:39 PM CST
File Name :code/hdu/2521.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=5005;
int num[N];
int factor( int n)
{
if (n==1) return 1;
int res = 2 ;
int mx = n;
for ( int i = 2 ; i < mx ; i++)
if (n%i==0)
res = n/i==i?(res+1):(res+2),mx=n/i;
return res;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("code/in.txt","r",stdin);
#endif
for ( int i = 1 ; i <= 5000 ; i++) num[i] = factor(i);
int T;
cin>>T;
while (T--)
{
int a,b;
scanf("%d%d",&a,&b);
int ans;
int mx = -1;
for ( int i = a; i <= b ; i++)
{
if (num[i]>mx)
{
mx = num[i] ;
ans = i;
}
}
printf("%d\n",ans);
}
#ifndef ONLINE_JUDGE
fclose(stdin);
#endif
return 0;
}