洛谷P1463:https://www.luogu.org/problemnew/show/P1463

思路

约数个数公式 

ai为质因数分解的质数的指数

定理:

设m=2a1*3a2*...*pak(其中p为第k大的质数)是Antiprime数 则必有a1≥a2≥a3≥...≥ak≥0

因此如果有两个值约数个数相同 则要取值比较小的那个

剪枝:

  1. 有了这个定理我们就可以搜索质数的指数 由于231已经远远超过数据规模 因此我们只需要搜到31层
  2. 质因子的个数最多只有10个(所有质因子相乘得到他们可以凑成的最大值)

代码

#include<iostream>
using namespace std;
int a[]={,,,,,,,,,,};//打表出前10个质数
long long n,s,s1;
void search(long long x,long long y,long long b,long long z)
{
if(x==) return;//第二个剪枝
long long k=;
for(int i=;i<=b;i++)//枚举每个质因子的范围
{
k*=a[x];//当前质因子有k个相乘
if(y*k>n) return;//超过范围就跳出
if(z*(i+)==s1&&y*k<s)
s=y*k;//如果两个值约数相等 取小的那个
if(z*(i+)>s1)//如果大于它 取大的那个
{
s1=z*(i+);
s=y*k;
}
search(x+,y*k,i,z*(i+));
}
}
int main()
{
cin>>n;
search(,,,); //分别为质因子个数 ans 指数层数 约数个数
cout<<s;
}

最新文章

  1. android studio 应用小知识总结
  2. Dynamic Invok Webservice
  3. 【原创】CHROME 最小字体限制为12PX的终极解决方案
  4. 护肤品总结 Skin Care (2)
  5. mysql去重的最方便的两种方法
  6. Python之路: socket篇
  7. 【2017-03-20】HTML基础知识、文字标记、图片标记、空格换行、表格、表格嵌套及布局、超链接
  8. Blockly编程:用Scratch制作游戏愤怒的小牛(小鸟)
  9. IEEE Trans 2007 Signal Recovery From Random Measurements via OMP
  10. 关于metaclass,我原以为我是懂的
  11. UNIX网络编程——UDP 中的外出接口的确定
  12. postman的安装与使用(模拟请求)
  13. Vue slot插槽内容分发
  14. String 和StringBuffer的简单实用案例
  15. 安装pod
  16. spring事务没回滚
  17. [转帖]Cgroups 与 Systemd
  18. 【bzoj4448】SCOI2015 情报传递
  19. Codeforces Round #425 (Div. 2) Misha, Grisha and Underground(LCA)
  20. Git系列四之在本地服务器搭建gitlab仓库管理

热门文章

  1. Android中用Java代码实现zip文件解压缩
  2. Android中的ListView点击时的背景颜色设置
  3. 解决引入外部文件(图片、js等)出现 403 net::ERR_ABORTED 的问题
  4. Javascript “等于”
  5. linux修改文件权限命令(chmod)
  6. C# ADO.NET面向对象想法
  7. 2017年10月30日 vs初级教学
  8. log4net写入DB2备忘 via OLEDB &amp; ODBC
  9. Android的Overlay机制
  10. zookeeper入门教程