【题解】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),c_i \ge c_{i+1}\)

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

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

证明：假设\(p_i\)不是\(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;
}