ZOJ 2562 More Divisors（高合成数）

ACM

题目地址：

题意： 

求小于n的最大的高合成数，高合成数指一类整数，不论什么比它小的自然数的因子数目均比这个数的因子数目少。

分析： 

网上都叫它反素数，事实上我查了一下，翻素数应该是正着写倒着写都是素数的素数。这个应该叫高合成数，见

高合成数有下面特征： 

where p1<p2<⋯<pk are prime, and the exponents ci are positive integers. 

Any factor of n must have the same or lesser multiplicity in each prime: 

p1^d1×p2^d2×⋯×pk^dk, 0≤di≤ci, 0<i≤k 

所以用回溯枚举。

代码：

/**  Author:      illuz 
     
      *  Blog:        http://blog.csdn.net/hcbbt*  File:        2562.cpp*  Create Date: 2014-08-06 20:45:53*  Descripton:  Highly Composite Number*/#include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;#define repf(i,a,b) for(int i=(a);i<=(b);i++)typedef long long ll;const int M = 1000;ll n;ll bestNum;ll bestSum;ll hcm[M][2];ll prim[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67};  // current is num, use the prim[k], sum of divisors, the limit of prim[k] you can usevoid getNum(ll num, int k, ll sum, int limit) {	if (sum > bestSum) {		bestSum = sum;		bestNum = num;	} else if (sum == bestSum && num < bestNum) {		bestNum = num;	}		ll p = prim[k];	for (int i = 1; i <= limit; i++, p *= prim[k]) {		// use i prim[k]s		if (num * p > n) break;		getNum(num *= prim[k], k + 1, sum * (i + 1), i);	}}// clac log2(n)int log2(ll n) {	int ret = 0;	ll p = 1;	while (p < n) {		p <<= 1;		ret++;	}	return ret;}// return the number of Highly Composite Number in [1, n]// and save the HCM in hcm[][2]int gethcm() {	int ret = 0;	n = 500000;		// [1, n]	while (n > 0) {		bestNum = 1;		bestSum = 1;		getNum(1, 0, 1, log2(n));		cout << bestNum << ' ' << bestSum << endl;		hcm[ret][0] = bestNum;		hcm[ret][1] = bestSum;		n = bestNum - 1;		ret++;	}	return ret;}int main() {	while (cin >> n) {		bestNum = 1;		bestSum = 1;		getNum(1, 0, 1, 50);		cout << bestNum << endl;	}}