【BZOJ 1053】[HAOI2007]反素数ant
BZOJ ant 素数
2023-09-14 09:03:44 时间
【链接】 我是链接,点我呀:)
【题意】
【题解】
用小的质数去凑那个数字。 显然比用大质数去凑划算。 因为 对于$x = p1^{q1}*p2^{q2}*...*pn^{qn}$ x的因子个数等于(q1+1)*(q2+1)....*(qn+1); 显然 你用的质数越小。 这个指数就能更大一点。 (表示相同的数字的情况下。至少不会更差。根据这个。
又有235....2329>2*10^9
则只要考虑这10个质数就可以了。
枚举它们用了多少个。
(即枚举各个质数的指数
(找出最优解就好。
【代码】
#include <bits/stdc++.h>
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define all(x) x.begin(),x.end()
#define pb push_back
#define ls l,mid,rt<<1
#define rs mid+1,r,rt<<1
using namespace std;
const double pi = acos(-1);
const int dx[4] = {0,0,1,-1};
const int dy[4] = {1,-1,0,0};
const int a[11] = {1,2,3,5,7,11,13,17,19,23,29};
LL n;
LL ansnum=-1,ansyueshu;
void dfs(LL cur,LL idx,LL cnt,LL yueshu){
if (idx>10) return;
//超过范围结束。
//cur大于n了,那么结束
if (cur>n) return;
if (ansnum==-1){
ansnum = cur;
ansyueshu = yueshu;
}else{
if (yueshu>ansyueshu){
ansnum = cur;
ansyueshu = yueshu;
}else if (yueshu==ansyueshu){
if (cur<ansnum){
ansnum = cur;
ansyueshu = yueshu;
}
}
}
//还是选择这个数字继续乘。
dfs(cur*a[idx],idx,cnt+1,yueshu/(cnt+1)*(cnt+2));
//选择下一个数字乘。
dfs(cur,idx+1,0,yueshu);
}
int main(){
#ifdef LOCAL_DEFINE
freopen("rush_in.txt", "r", stdin);
#endif
scanf("%lld",&n);
//当前数字,当前选择的是第几个数字,这个数字乘了几次,约数个数
dfs(1,1,0,1);
printf("%lld\n",ansnum);
return 0;
}
相关文章
- BZOJ 1695 [Usaco2007 Demo]Walk the Talk 链表+数学[通俗易懂]
- SP11444 MAXOR - MAXOR & bzoj 2741 【FOTILE模拟赛】L
- bzoj 4399: 魔法少女LJJ 题解
- bzoj 1052: [HAOI2007]覆盖问题 & Luogu P2218 [HAOI2007]覆盖问题 题解
- Luogu P2493 [SDOI2011]贪食蛇 & bzoj 2284. [Sdoi2011]贪食蛇 题解
- bzoj 3091 & Luogu P4842 城市旅行 题解
- bzoj 2959 长跑 题解
- bzoj 3653 谈笑风生 题解
- bzoj 3209 & Luogu P4317 花神的数论题 题解
- bzoj 1858. [Scoi2010]序列操作 题解
- bzoj 4337 BJOI2015 树的同构
- bzoj 4491. 我也不知道题目名字是什么 题解
- bzoj 2006. [NOI2010]超级钢琴 题解
- ANT轻松完成Linux命令执行(ant执行linux命令)
- Linux下如何配置Ant?(linux配置ant)
- 使用Linux系统运行Ant构建工具(linux运行ant)
- 使用Linux操作系统安装Ant的步骤指南(linux安装ant)
- Linux 系统下如何安装 Ant?(linux安装ant)
- 如何彻底卸载Linux系统上的Ant?(linux卸载ant)
- 如何在Linux上安装Ant(ant安装linux)
- 数据库使用Ant实现快速部署Oracle数据库(ant创建oracle)