bzoj1225 [HNOI2001] 求正整数
2024-08-24 02:12:47
1225: [HNOI2001] 求正整数
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 762 Solved: 313
[Submit][Status][Discuss]
Description
对于任意输入的正整数n,请编程求出具有n个不同因子的最小正整数m。例如:n=4,则m=6,因为6有4个不同整数因子1,2,3,6;而且是最小的有4个因子的整数。
Input
n(1≤n≤50000)
Output
m
Sample Input
4
Sample Output
6
分析:这道题和反素数这道题非常像.
涉及到因数个数,可以很容易想到公式(k1 + 1) * (k2 + 1) *......*(kn + 1),那么先把可能的质数给求出来,枚举次数.这道题我们是预先知道了因数的个数,那么枚举的次数就要满足条件:+1后整除因数个数。dfs一下答案就出来了
但是这样要用到高精度,每一次都高精度很麻烦啊,能不能在中间过程时不用高精度呢?可以的,只要我们在运算的时候取对数就好了.目的就是方便比大小,不用高精度,最后输出的时候用高精度就可以了.
只涉及到高精度数比大小并且满足对数运算律似乎都可以用对数运算来避免中途高精度运算.我感觉目前只能用到log(xy) = logx + logy和logx^k = k*logx,在搜索的时候分步运算合并即可.
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cfloat> using namespace std; int n,prime[] = {,,,,,,,,,,,,,,,,},tot = ;
double minn = DBL_MAX,llg[];
int res[],ans[],p[],len; void print()
{
len = p[] = ;
for (int i = ; i <= ; i++)
{
for (;ans[i] > ;ans[i]--)
{
for (int j = ; j <= len; j++)
p[j] *= prime[i];
for (int j = ; j <= len; j++)
{
p[j + ] += p[j] / ;
p[j] %= ;
}
if (p[len + ])
len++;
while (p[len] / != )
{
p[len + ] += p[len] / ;
p[len] %= ;
len++;
}
}
}
for (int i = len; i >= ; i--)
printf("%d",p[i]);
printf("\n");
} void dfs(double sum,int cnt,int x)
{
if (sum >= minn)
return;
if (cnt == )
{
minn = sum;
memset(ans,,sizeof(ans));
for (int i = ; i <= x - ; i++)
ans[i] = res[i];
return;
}
if (x > )
return;
for (int i = ; (i + ) * (i + ) <= cnt; i++)
if (cnt % (i + ) == )
{
res[x] = i;
dfs(sum + i * llg[x],cnt / (i + ),x + );
if ((i +) * (i + ) != cnt)
{
res[x] = cnt / (i + ) - ;
dfs(sum + (cnt / (i + ) - ) * llg[x],i + ,x + );
}
}
} int main()
{
scanf("%d",&n);
for (int i = ; i <= ; i++)
llg[i] = log(prime[i]);
dfs(,n,);
print(); return ;
}
最新文章
- 工程中建立多个src目录
- 实战录 | Kafka-0.10 Consumer源码解析
- Docker总结(图片打开略慢请知晓)
- springMVC-配置Bean
- xcode免证书开发
- Dom初
- iOS沙盒机制的基本操作总结
- u-boot启动流程分析(2)_板级(board)部分
- Form表单学习网站
- 关于 ASP.NET vNext
- [Reactive Programming] Using an event stream of double clicks -- buffer()
- php遍历数据库
- IOS开发——手动设置屏幕旋转
- R语言&;页游渠道分析(转)
- Python网络编程socket练习(TCP)
- Django中过期@cache_page中缓存的views数据
- [模板] BSGS/扩展BSGS
- cocos creator 刚体卡顿问题(边界会卡住)
- 创建和使用动态链接库(转)vs2008 vs2010
- 理解套接字Socket