[总结] 反素数

素数的定义可以为：因子只有2个的数（一个是1，另一个是本身），也就是因子最少的数。

那么，反素数可以定义成因子数最多的数，假如因子个数相同那么是最小的那个数，反素数是相对于一个集合来说的（比如在 $n$ 个数以内的数）。

简而言之，因素最多并且值最小的数，就是反素数。

朴素求法：利用整数唯一分解定理若 $x=p_1^{k_1}p_2^{k_2}…p_n^{k_n}$ ，那么 $x$ 就有 $(k_1+1)(k_2+1)…(k_n+1)$ 个因数。给某个集合扫一遍求下 $max$ 即可。

反素数有两个特点：

反素数肯定是从 $2$ 开始的连续素数的幂次形式的乘积。
数值小的素数的幂次大于等于数值大的素数： $x=p_1^{k_1}p_2^{k_2}…p_n^{k_n}$ ，那么有 $k1 \geq k2 \geq…k_n$ 。

解释：

反证，若存在不从 $2$ 开始的连续素数之积 $p$ ，那么必然存在一个从2开始的连续素数之积 $q$ ，除了一个 $2$ 以外，其他值均与 $p$ 相等，而此时 $q < p$ 。
若存在 $k_i, k_j$ ，使得 $i<j,k_i>k_j$ 成立。那么我们可以交换一下 $p_i$ 与 $p_j$ ，使得这个数更小。

想要求给定自然数 $n$ ，求 $[1,n]$ 内的反素数。这个问题似乎没有什么更加牛X的解决方法，实际上还是要通过枚举的方法，为了解决这个问题，我们再提出两个问题：

对于给定的 $n$ ，要枚举到哪一个素数：枚举到 $\leq n$ 的素数就可以。
枚举多少次幂：实际上枚举到最小素数 $p$ 的 $k$ 次幂，使得 $p^k>n$ ，那么枚举到的最大幂次肯定要小于 $k$ 。

一般这类问题都是DFS+一些分支限界枚举答案的。

练习1：http://codeforces.com/contest/27/problem/E

题意：找含有 $n$ 个因子的最小的那个数，这个数不超过1E18。

分析：

设这个数字是 $m$ ，那么可以设 $m=p_1^{k_1}p_2^{k_2}…p_r^{k_r}$ ，其中 $(k_1+1)(k_2+1)…(k_r+1)=n$ 。我们由上述结论1可以求出来 $p_i$ 的上界：取 $k_1=$ 2，那么最多也就是 $\lceil log_21000 \rceil=10$ 个不同的素数，贪心取最小的前10个素数就可以。~~分析到这里就可以打表了。~~
再考虑这个数在1E18内的问题，也就是 $k$ 的取值范围。取最小的 $p=2$ ，那么顶多是60层。

于是我们就可以DFS，在每层（即每个素数）暴力枚举这个数选取次数，然后维护上一层的数值以及因数个数就行了。

#include <bits/stdc++.h>
using namespace std;

using ull = unsigned long long;
const int maxn = 111;
int n;
int p[maxn] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
ull ret;

void dfs(int depth, ull cur, int cnt, int hi) {
  if(depth >= 11 || cnt > n) return;
  if(cnt == n) {
    ret = min(ret, cur);
    return;
  }
  for(int i = 1; i <= hi; i++) {
    if(cnt * (i + 1) > n) break;
    cur *= (ull)p[depth];
    dfs(depth+1, cur, cnt*(i+1), i);
  }
}

signed main() {
  // freopen("in", "r", stdin);
  while(~scanf("%d",&n)) {
    ret = 1E18;
    dfs(1, 1, 1, 60);
    cout << ret << endl;
  }
  return 0;
}