【反素数】

news/2024/9/29 11:49:39/

题目

思路

  • 首先分析 x 的性质
    • 一定是 x \in [1,N] 中约数最大的
    • 一定是约数同是最大的数字中值中最小的
  • 进一步挖掘性质,紧贴枚举的做法
    • 约数最大值最小(也决定了层数、其它约束),是枚举的比较条件
    • 实现上述目的,枚举的质数种类在大小上是连续的,指数是不严格单调递减的(分支方式)
  • 分析采取的方案
    • 通过 dfs 枚举质因子数目来枚举不同的 x
    • 用约数公式判断约数个数进行比较
  • 准备枚举(深搜)
    • 比较条件:约数最大值最小
    • 深搜的层数:枚举到 9 种质数就结束
    • 分支方式:当前质因子不同的指数
    • 其它约束:值不超过 n

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;int n;
int p[9] = {2,3,5,7,11,13,17,19,23};
int min_num = INT_MAX, max_s;
void dfs(int u, int last, int num, int s)
{if(s > max_s || s == max_s && num < min_num){max_s = s;min_num = num;}if(u >= 9) return;LL mi = 1;for(int i = 1; i <= last; i++){mi *= p[u];if(num * mi > n) break;dfs(u+1, i, num * mi, s * (i+1));}
}
int main()
{cin >> n;dfs(0, 30, 1, 1);cout << min_num;return 0;
}


http://www.ppmy.cn/news/1531901.html

相关文章

mysql如何替换数据库所有表中某些字段含有的特定值

目录 背景查询所有表名查询表的所有字段过虑特征字段替换字段中含有的特定值 背景 公司的测试域名更换了&#xff0c;导致存放在数据库中的域名也要跟着替换&#xff0c;当然把域名存放在数据库表中是不科学的&#xff0c;不建议这样做&#xff0c;但公司的同事就这样做了&…

CSS 的背景样式

1.1 背景颜色 1.2 背景图片 1.3 背景平铺 1.4 背景图片位置 1.4.1 方位名词 1.4.2 精确单位 1.4.3 混合单位 1.5 背景图像固定 1.6 背景复合写法 1.7 背景色半透明 1.8 总结

UE学习篇ContentExample解读------Blueprints Advanced-下

文章目录 总览描述批次阅览2.1 Timeline animation2.2 Actor tracking2.3 Button Trigger using a blueprint interface2.4 Opening door with trigger2.5 Child Blueprints 概念总结致谢&#xff1a; 总览描述 打开关卡后&#xff0c;引入眼帘的就是针对关卡的总体性文字描述&…

抖店电商怎么使用云账户解决资金提现?

多平台流水资金统一进入电商客户在银行的资金监管专户中&#xff0c;直接向各供应商、各经销商分账结算 可将某淘、某猫、某东、拼某某、抖某等多家电商平台的结算资金统一结算到银行专用监管专户&#xff0c;在我们的系统中完成与供应链厂商的分账和结算&#xff0c;实现了资…

Redis:持久化

1. Redis持久化机制 Redis 支持 RDB 和 AOF 两种持久化机制&#xff0c;持久化功能有效地避免因进程退出造成数据丢失问题&#xff0c; 当下次重启时利⽤之前持久化的文件即可实现数据恢复。 2.RDB RDB 持久化是把当前进程数据⽣成快照保存到硬盘的过程&#xff0c;触发 RDB…

kubernets资源相关内容介绍

文章目录 kubernets资源基本结构示例&#xff1a;Deployment资源配置文件解析常见资源类型复杂配置总结 各种资源之间的关系1. Pods与其他资源的关系2. Services与其他资源的关系3. Deployments与其他资源的关系4. StatefulSets与Pods5. DaemonSets与Pods6. ConfigMaps、Secret…

vmware 里 centos7 扩展 /dev/mapper/centos-root 容量

虚拟机安装centos7.9 的时候分配了10G磁盘&#xff0c;后来不够用了。 第一步 在虚拟机设置里&#xff0c;硬盘里扩展 磁盘容量&#xff0c;这里只能往大扩&#xff0c;不允许往小设置。 第二步&#xff0c;centos7 里查看现有分区情况 [rootvm159 ~]# df -h 文件系统 …

Flutter InAppWebView 路由导航处理

flutter InAppWebView路由导航处理&#xff0c;有以下两种处理方案&#xff1a; H5层控制路由&#xff0c;H5拥有自己的路由&#xff0c;当返回到跟路由root时&#xff0c;此时点击跟节点&#xff0c;通过jsbridge调用flutter提供的方法来关闭当前widget&#xff0c;flutter关…