洛谷 P1128 [HNOI2001]求正整数

来源：爱问旅游网

题目描述

对于任意输入的正整数n，请编程求出具有n个不同因子的最小正整数m。

例如：n=4，则m=6，因为6有4个不同整数因子1，2，3，6；而且是最小的有4个因子的整数。

输入输出格式

输入格式：

n（1≤n≤50000）

输出格式：

输入输出样例

输入样例#1：

输出样例#1：

很显然，这道题需要高精度，因为，如果， $n$ 为一个素数，那么答案一定是 $2^{n-1}$

① 最多只会用到 $16$ 个素数，因为2^16>50000。

② $now$ 表示当前最优分配方案所得出的最小的答案， $k[i]$ 为该数分解成p[i]的个数， $w[i]$ 数组表示 $p[i]^{k[i]}$ 的值（w[i]一定会要用到高精度的，所以是用数组表示）

③ 很显然， $(k[0]+1)*(k[1]+1)*…*(k[15]+1)$ 为一个数拥有不同因子的个数

④ 把n分解成x个素数相乘的形式，从小到大排序后形成一个数组 $a[0],a[1],…,a[x]$

⑤ 对于数组 $a$ 中的每个数都会被分配到 $k$ 中某一个位置 $i$ 上，求出分配到 $i$ 位置上时 $now$ 变大了多少，找出 $now$ 改变量最小的那个位置 $p$ 作为这次分配的位置，更新 $w[p]$ ， $k[p]$ ， $now$ ，一个贪心的想法

⑥ 将 $a$ 中所有的答案分配完时的 $now$ 即为答案

自认为正确的一个思路，如有错误，欢迎dalao指出

由于，本人比较懒（高精度代码量比较大），然后就没打代码了，见谅

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文