[总结] 反素数

发表于 | 更新于 | 分类于 | 评论数： | 阅读次数：

素数的定义可以为：因子只有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$即可。

反素数有两个特点：

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

解释：

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

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

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

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

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

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

分析：

  1. 设这个数字是$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个素数就可以。分析到这里就可以打表了。
  2. 再考虑这个数在1E18内的问题，也就是$k$的取值范围。取最小的$p=2$，那么顶多是60层。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#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;
}