ZOJ 2562 More Divisors（高合成数）
ACM
题意：
求小于n的最大的高合成数，高合成数指一类整数，不论什么比它小的自然数的因子数目均比这个数的因子数目少。
分析：
网上都叫它反素数，事实上我查了一下，翻素数应该是正着写倒着写都是素数的素数。这个应该叫高合成数，见Wikipedia: Highly composite number
高合成数有下面特征：
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 <iilluzen[at]gmail.com>
* Blog: http://blog.csdn.net/hcbbt
* File: 2562.cpp
* Create Date: 2014-08-06 20:45:53
* Descripton: Highly Composite Number
*/ #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
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 use
void 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;
}
}