51nod 1060 最复杂的数

51nod 1060 最复杂的数

题目大意：

把一个数的约数个数定义为该数的复杂程度，给出一个n，求1-n中复杂程度最高的那个数。(n\le 10^{18}, T\le 100)
例如：12的约数为：1 2 3 4 6 12，共6个数，所以12的复杂程度是6。如果有多个数复杂度相等，输出最小的。
即求 n 以内最大的反素数。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int p[16] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
ll n;
ll ans, cnt;
// ans为n以内的最大反素数（会持续更新），cnt为ans的因子数。

void dfs(int dep, ll tmp, ll num, int up) {
    if (dep >= 16 || tmp > n) {
        return;
    }
    if (num > cnt || (num == cnt && ans > tmp)) {
        ans = tmp;
        cnt = num;
    }
    for (int i = 1; i <= up; i++) {
        if (tmp > n / p[dep]) {
            break; // 防止爆long long
        }
        // temp每次乘一个当前素数并向后dfs
        // 后面素数连乘的个数不可能超过前面的
        dfs(dep + 1, tmp *= p[dep], num * (i + 1), i);
    }
}
int main() {
    int T; scanf("%d", &T);
    while(T--) {
        scanf("%lld", &n);
        cnt = 0;
        dfs(0, 1, 1, 60);
        printf("%lld %lld\n", ans, cnt);
    }
    return 0;
}