【题解】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 |
|