计算小于n的数中,约数个数最多的数,若有多个最输出最小的一个数。

http://hihocoder.com/problemset/problem/1187

对于100有 60 = 2 * 2 * 3 * 5,共 (2 + 1) * (1 + 1) * (1 + 1) = 12个约数。

对于 n <= 10 ^ 16,int最大值为10位,所以这里要用long long。很显然:约数要尽量小,然后小的约数的指数一定大于大的约数的指数。

所以对于 10^16,有质因子:2,3,5,7,11,13,17,19,23,29,31,37,41,43,47...后面的可以不考虑了。

#include <cstdio>
#include <cmath> int p[] = {, , , , , , , , , , , , , , };
long long n, result = << ;
int maxDivisors = ; void dfs(long long res, int divisors, int np, int ti) {
if (np > || res > n) return;
if (divisors > maxDivisors || (divisors == maxDivisors && res < result)) {
maxDivisors = divisors;
result = res;
}
int t = p[np];
int i = ;
long long val;
while ((val = res * std::pow(t, i)) < n && i <= ti) {
dfs(val, divisors * (i + ), np + , i);
++i;
}
} int main() {
scanf("%lld", &n);
dfs(, , , );
printf("%lld\n", result);
return ;
}

最新文章

  1. 利用T-Sql语句中的二重循环打印乘法口诀表
  2. HTML5+JS 《五子飞》游戏实现(五)移动棋子
  3. INSTALL_FAILED_INSUFFICIENT_STORAGE
  4. 解决SQL Server 2008 64位系统无法导入Access/Excel的问题 2012/08/01
  5. ServiceStack
  6. HBase(七): HBase体系结构剖析(下)
  7. 免费LInux主机资源
  8. Java 实现享元(Flyweight)模式
  9. Swift - 使用UIWebView和UIToolbar制作一个浏览器
  10. boost::format(字符串格式化库)
  11. thinkphp后台向前台传值没有传过去的小问题
  12. 【题解】狼抓兔子—BZOJ1001。
  13. 基于ASP.NET MVC 下的Extjs的Combbox加载速率问题,终于解决啦:)
  14. Git 基础 - 打标签
  15. IOS 内存斗争小史之 对象、指针、内存的基本理解
  16. npm配置镜像、设置代理
  17. thinkphp5.0 获取请求信息
  18. avalonJS-源码阅读(3) VMODEL
  19. 【java规则引擎】《Drools7.0.0.Final规则引擎教程》第4章 4.3 日历
  20. DevExpress中Tile Application窗体的模型架构图

热门文章

  1. 转 java中的session
  2. yii2框架原生的结合框架使用的图片上传
  3. Bash:-变量替换后利用大括号获取数字存在的间隔
  4. Python学习笔记-常用模块
  5. 【web必知必会】——图解HTTP(上)
  6. EF中使用linq进行关联查询
  7. easyui datagrid 仿ext—右键
  8. MAC地址泛洪攻击测试
  9. MVC 4 用Nuget安装组件后的常见错误
  10. jsp表格数据导出到Execl