题目来源：URAL 1748. The Most Complex Number

题意：求一个小于等于n的因子最多的数

思路：搜索+剪枝

#include 
  
   
#include 
   
     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; }