ZOJ（2562 More Divisors 求反素数经典应用！）

题目大意：给一个N求不超过N的 哪个数的因子数最多，数目相同的取值小的那个！

题目分析：这里引进反素数知识：

反素数第一点：g(x)表示 x含有因子的数目，设 0<i<=x  则g(i)<=x;

反素数第二个特性：2^t1*3^t2^5^t3*7^t4..... 这里有 t1>=t2>=t3>=t4...

所以我们根据这两个属性 进行递归求解！

递归过程：

首先做出三条判断，第一是否该值不超过N的大小，第二比较因子的个数，更新最大的，即更新最大的反素数，第三如果因子数相等，则更新较小的。

然后枚举+递归不断尝试更新，使得得到因子数最大的那个！

代码+部分注释：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
long long bestres,bestsum,n;
long long pri[16]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};
//res表示当前讨论的值，sum表示该值的因子数目，
//k表示讨论到第几个素数了，limit表示上次的幂的值
//这次幂的上限，就是体现t1>=t2>=t3...
void work(long long res, long long sum,int k,int limit ){
	if(res>n)//如果超过n就跳出！
		return ;
	if(sum>bestsum){
      //这次计算的因子数目比我以前过程的最大值还大，那么就要更新！
		bestres=res;
		bestsum=sum;
	}
	if(sum==bestsum&&res<bestres){
//如果因子数目一样，取值比较小的！
		bestres=res;
	}
	long long p=pri[k];
//记得第一次p=pri[k],因为下面i是从1开始计数的！
	for(int i=1;i<=limit;i++,p*=pri[k]){
		if(res*p>n)
			break;
		else
			work(res*p,sum*(i+1),k+1,i);
	}
}
int main(){
	while(scanf("%lld",&n)!=EOF){
		bestres=1LL;
		bestsum=1LL;
		work(1LL,1LL,0,50);
		printf("%lld\n",bestres);
	}
	return 0;
}