首页 > 代码库 > URAL 1748. The Most Complex Number 反素数
URAL 1748. The Most Complex Number 反素数
题目来源:URAL 1748. The Most Complex Number
题意:求一个小于等于n的因子最多的数
思路:搜索+剪枝
#include <cstdio> #include <cstring> using namespace std; typedef unsigned __int64 LL; LL prime[16] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53}; LL num, sum, n; void dfs(int p, int q, LL x, LL y) { if(p >= 16) return; if(x > n) return; if(y > sum) { num = x; sum = y; } if(y == sum && num > x) num = x; for(int i = 1; i <= q; i++) { double tmp = (double)x; if(tmp*prime[p] > n) break; dfs(p+1, i, x *= prime[p], y*(1+i)); } } int main() { int T; scanf("%d", &T); while(T--) { scanf("%I64u", &n); sum = 0; dfs(0, 60, 1, 1); printf("%I64u %I64u\n", num, sum); } return 0; }
URAL 1748. The Most Complex Number 反素数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。