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;

	}

}