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

题目链接(洛谷)

题目大意

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

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

分析

唯一分解定理:根据乘法原理,对于唯一分解的第个因数有种选择(),的因数个数为

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

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

证明:假设,那么对应的值为,前面我们设,当我们把两指数的位置交换时,显然有,则是不是最小,与题设矛盾。

  • 后的第一个质数。

证明:假设不是后第一个质数,那么设后第一个质数为,有,则不是最小,与题设矛盾。

具体实现用。由于前个质数的乘积,我们对于前个质数枚举其指数;又因为 ,指数枚举到即可。

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

实现

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;
}