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