洛谷 P1128 [HNOI2001] 求正整数
题目描述
对于任意输入的正整数n，请编程求出具有n个不同因子的最小正整数m。
例如：n=4，则m=6，因为6有4个不同整数因子1，2，3，6；而且是最小的有4个因子的整数。
输入输出格式
输入格式：
n（1≤n≤50000）
输出格式：
m
输入输出样例
输入样例#1：
INT.IN
4
输出样例#1：
INT.OUT
6
【分析】
一道神题，昨天模拟赛的t2，然而昨天太浪了，就没有做（谴责）。
我相信许多人和我一样刚看了这道题一定会不知所措，接下来就分析一下。
题目中给了这个正整数的因数个数，并不好处理，如果是质因数就好处理多了。
介绍一下约数公式：n=Πpri[i]*a[i]（n是这个数的因数个数，pri是质数，a是指数）。
我就不证明了，我也不会。
数据范围只有50000，计算可得约数个数最多16个，先打出一张素数表，以后的质数对答案没有贡献。
dfs(x,y,z)——x表示搜索到的正整数，y表示x的因数个数，z表示已经搜索到了第z个质数。
这样是会超时的，考虑剪枝。
枚举当前质数的指数i时，y%(i+1)==0，那么就是求y的因数，时间复杂度sqrt(y)。 当前质数的质数不可以为0，因为是从小到大搜索，还是比较有用的。 12
又发现x是会爆long long的（比赛时用double卡的精度）如果搜索时加高精度就太麻烦了，考虑用对数。
log(n)=Σa[i]*log(pri[i])（自己推吧，字母代表的意义和上面一样）。
搜索时保存指数，最后加一个高精度就好了。
听说还可以用dp，可我不会。
【代码】
//min #include<cmath> 123
相关知识
华罗庚竞赛题：已知a+b+ab=32，且a、b为正整数，求a+b的值
中考常考知识《完全平方式》，已知a+1/a=3，求a⁴+1/a⁴
【数列{an},a1=2,an+1=2an+n（n是正整数）,则其通项公式是什么】
探秘凤凰谷，宠物玩乐天堂！
【菲洛】
求魔兽世界最新的全部的稀有宠物坐标! ， 魔兽世界怀旧服稀有宠物有哪些
洛江宠物雕塑
65 洛伦兹
原创 0-4！1-4！利物浦2次被掀翻，赢下曼城=进决赛，克洛普剑指4冠王
卡洛沙金刚鹦鹉
网址: 洛谷 P1128 [HNOI2001] 求正整数 https://m.mcbbbk.com/newsview182065.html
| 上一篇: thymeleaf常用注解 |
下一篇: QQ宠物QQ宠物中如何获得克扣币 |
