【题解】CF27E Number With The Given Amount Of Divisors

发表于 分类于 阅读次数： Valine：

题目链接（洛谷）

题目大意

给定一个正整数$n$，输出最小的整数，满足这个整数有$n$个因子。

$1\le n \le 1000$，保证答案$<10^{18}$

分析

唯一分解定理：根据乘法原理，对于唯一分解$x=\prod{i=1}^k p_i^{c_i}$，$x$的第$i$个因数有$c_i+1$种选择（$0 \to c_i$），$x$的因数个数为$\prod{i=1}^k (c_i+1)$。

设$x$是因数个数为$n$的最小的数，考虑$x$的性质：

对于$x$的唯一分解形式：$x=\prod_{i=1}^k p_i^{c_i}$，不妨设$p_1<p_2<p_3<…<p_k$。

  • 有$\forall i \in [1,k),ci \ge c{i+1}$

证明：假设$ci<c{i+1}$，那么对应的值为$pi^{c_i}\times p{i+1}^{c{i+1}}$，前面我们设$p_i<p{i+1}$，当我们把两指数的位置交换时，显然有$pi^{c_i}\times p{i+1}^{c{i+1}}>p_i^{c{i+1}}\times p_{i+1}^{c_i} $，则是$x$不是最小，与题设矛盾。

  • 有$p1=2$且$\forall i \in (1,k],p_i$为$p{i-1}$后的第一个质数。

证明：假设$pi$不是$p{i-1}$后第一个质数，那么设$p_{i-1}$后第一个质数为$q$,有$p_i^{c_i}>q^{c_i}$，则$x$不是最小,与题设矛盾。

具体实现用$\text{DFS}$。由于前$16$个质数的乘积$>10^{18}$，我们对于前$16$个质数枚举其指数；又因为 $2^{64}>10^{18}$，指数枚举到$64$即可。

按照前面两条性质可行性剪枝$+$最优性剪枝。

实现

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
32
33
34
35
36
37
38
39
40
#include<bits/stdc++.h>

#define ll unsigned long long
using namespace std;
const ll lim = 1e18;
int n;
ll pri[] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};
ll ans = lim + 1;

ll qp(ll a, ll b) {
    ll ans = 1, base = a;
    while (b > 0) {
        if (b & 1) {
            ans *= base;
        }
        base *= base;
        b >>= 1;
    }
    return ans;
}

void dfs(int x, ll sum, int num, int lst) {
    if (sum > lim || sum >= ans || sum < 0) return;
    if (num > n) return;
    if (x > 16) return;
    if (num == n) {
        ans = min(ans, sum);
        return;
    }
    for (int i = 1; i <= lst; i++) {
        dfs(x + 1, sum * qp(pri[x], i), num * (i + 1), i);
    }
}

int main() {
    cin >> n;
    dfs(1, 1, 1, 64);
    cout << ans;
    return 0;
}