题目地址
http://acm.bnu.edu.cn/bnuoj/external/57/5772.pdf
题目大意：
给一个数字n (n < 75)。求最小的X ， 满足 X = Y * Z (Y <= Z) 有n种方式
分析：
此题跟我航出的Anti-Prime 反素数的题目类似， 都是直接搜索+枚举答案就好。
解法：
0、 筛法求素数。 因为n <= 75 ， 因此理论上只用求出前75个（或者更小就不细算了） 质数就行。
1、对一般情况的判定（不包括 X = Y * Y 即平方数的问题）
显而易见， 如果 X != Y * Y ， 那么X肯定会有 N * 2 个因数。因此，只要枚举最小的有 M （= N * 2 ）个因数的数就可以。方法是搜索：
dfs（LL now , LL step , LL cnt） 状态是 当前的乘积是 now ， 已经步行到第step个素数（2 ， 3 ， 5 ， 7 ， 11 ， 13.。。。）， 现在一共有cnt个因数。
对于第step个因数， 如果有k个， 即下一个状态是 now * $ prime[step] ^{k} $ 时， 很明显因数个数增加了(k + 1) 倍，于是下一个状态就是
dfs(now * $ prime[step] ^{k} $ , step + 1 , cnt * (k + 1) )
剪枝：
初始化ans = $2^{18}$ ， （题目保证了答案一定小于等于这个数） ， 然后对于每次转移时 ， 如果 now * prime[step] > ans 的时候break
2、对于平方数的情况， 不妨考虑这两个数：4 ， 36
4 = 1 * 4 = 2 * 2 = （分解质因数为） $2^{2}$ ， 按照先前的算法应该有 2 + 1 = 3个因数，而 n = 2
36 = 1 * 36 = 2 * 18 = 3 * 12 = 4 * 9 = 6 * 6 = (分解质因数为) $2^{2}*3^{2}$ ， 按照先前的算法应该是有 （2 + 1）* （2+ 1） = 9 个因数，而 n = 5
为什么呢？因为对于n来说，有两个因数重合。那么对于平方数来说，只需要 n * 2 - 1 个因数就可以。因为必须是完全平方数，于是每个因数的幂就必须是偶数。只用在搜索的时候特判就好了。
至此，这个问题就被完美的解决了。
代码：
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
#define LL long long
const int PRIMERANGE = 300;
const LL inf = 1e18;
int prime[PRIMERANGE + 1];
int getPrime(){ // 筛法求素数， 模板
memset(prime , 0 , sizeof(prime));
for (int i = 2 ; i <= PRIMERANGE ;++i){
if (!prime[i]) prime[++prime[0]] = i;
for (int j = 1 ; j <= prime[0] && prime[j] <= PRIMERANGE / i ; j++){
prime[prime[j] *i ] = 1;
if (i % prime[j] == 0) break;
}
}
return prime[0];
}
LL n;
LL ans;
void dfs(LL now , LL step, LL cnt){ // 不考虑平方的情况
if (cnt == n){
ans = min<LL>(ans , now); //记录当前最佳答案
return;
}
LL last = n / cnt;
for(LL i = 1 ; i <= last ; ++i){ // 枚举prime[step]的幂
if (prime[step] * now > ans) break; //剪枝
now *= prime[step];
if (last % (i + 1 )) continue; // 剪枝， 如果 cnt * (i + 1) 不是n的约数那么放弃
dfs(now , step + 1 , cnt* (i + 1)); // 状态转移
}
}
void dfssquare(LL now , LL step, LL cnt){ // 特判完全平方数
if (cnt == n){
ans = min<LL>(ans , now);
return;
}
LL last = n / cnt;
for(LL i = 2 ; i <= last ; i += 2){ // 幂必须为偶数
if (now * prime[step] > ans) break;
now *= prime[step] * prime[step];
//if (now > ans) break;
if (last % (i + 1 )) continue;
dfssquare(now , step + 1 , cnt* (i + 1));
}
}
void solve(){
n*= 2; // 忽略完全平方数的情况
ans = inf;
dfs(1 , 1 , 1);
LL other = ans;
ans = inf;
n /= 2; // 特判完全平方数
n = 2 * n - 1;
dfssquare(1 , 1 , 1);
ans = min<LL>(ans , other); // 答案取小
printf("%I64d\n" , ans);
}
int main(){
getPrime();
while(cin >> n , n) solve();
}