Backtrack kết hợp với tham lam, theo công thức tính số ước nguyên dương của một số thì ta chỉ quan tâm tới bậc của các thừa số nguyên tố chứ không quan tâm đến giá trị của các thừa số nguyên tố đó. Vì để số đó nhỏ nhất có thể (đảm bảo nhỏ hơn hoặc bằng ~n~) thì ta ưu tiên chọn các thừa số nguyên tố nhỏ nhất, tầm ~20~ số đầu (vì tích ~20~ số nguyên tố đầu tiên đủ lớn hơn ~10^{18}~), và xét bậc của các thừa số nguyên tố đó giảm dần.

Độ phức tạp tối đa: số nghiệm nguyên không âm của bất phương trình: ~a_1 + a_2 + \dots + a_{20} \leq 60~ ~(a_1 \geq a_2 \geq ... \geq a_{20})~ ( xấp xỉ ~5 * 10^6~ nghiệm) nhưng thực tế chạy nhanh hơn rất nhiều.

Code mẫu:

#include <bits/stdc++.h>

using namespace std;

vector <int> primes;
long long N, res;

void init(void) {
    for (int i = 2; (int) primes.size() < 20; ++i) {
        bool check = true;
        for (int j = 2; j * j <= i; ++j) if (i % j == 0) check = false;
        if (check) primes.push_back(i);
    }
}

void backtracking(int i, int maxExp, long long val, long long numDiv) {
    res = max(res, numDiv);
    if (i == (int) primes.size()) return;
    for (int d = 1; d <= maxExp; ++d) {
        if (N / primes[i] < val) return;
        val *= primes[i];
        backtracking(i + 1, d, val, numDiv * (d + 1));
    }
}

long long process(void) {
    cin >> N;
    res = -1;
    backtracking(0, 64, 1, 1);
    return res;
}

int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    init();
    int t; cin >> t;
    while (t--) cout << process() << '\n';
    return 0;
}