给定一个整数 n，找出不超过 n 的所有整数中，拥有最多约数的数。如果有多个数具有相同的最大约数数量，则输出其中最小的那个。

输入

一行包含一个整数 n。

对于 30% 的数据，n ≤ 10³。

对于 100% 的数据，n ≤ 10¹⁶。

输出

一行输出结果。

样例输入

100

样例输出

60

题解

将一个正整数 N 进行质因数分解，得到：

N = p₁^k₁ \* p₂^k₂ \* ... \* p_m^k_m

(其中 p₁ < p₂ < ... < p_m 是质数)

N 的约数个数为 (k₁+1) \* (k₂+1) \* ... \* (k_m+1)。

我们要求的是不超过 N 的数中，约数个数最多且数值最小的数。记为 s(N)。

我们可以推导出 s(N) 的质因数分解形式具有以下特点：

1. s(N) = 2^k₁ \* 3^k₂ \* 5^k₃ \* ... \* p_i^k_i \* ...
2. k₁ ≥ k₂ ≥ k₃ ≥ ... ≥ k_m (指数单调不增)

换句话说，s(N) 的质因子必须是连续的质数，并且它们的指数是非递增的。

因此，我们可以使用深度优先搜索 (DFS) 的方法来求解。

实现细节

前 14 个质数的乘积大约为 1.3 x 10¹⁶。这意味着搜索的深度最多为 13 层。搜索复杂度可以粗略估计为 2¹³，对于此问题来说是足够高效的。

代码实现

#include <iostream>
#include <vector>
#include <algorithm>

typedef long long ll;

std::vector<int> primes;
ll max_divisors_count = 0;
ll result_number = 1;
ll limit_n;

// 预计算前一些小的质数
void sieve(int limit) {
    std::vector<bool> is_prime(limit + 1, true);
    is_prime[0] = is_prime[1] = false;
    for (int p = 2; p * p <= limit; ++p) {
        if (is_prime[p]) {
            for (int i = p * p; i <= limit; i += p)
                is_prime[i] = false;
        }
    }
    for (int p = 2; p <= limit; ++p) {
        if (is_prime[p]) {
            primes.push_back(p);
        }
    }
}

// 深度优先搜索函数
// prime_idx: 当前考虑的质数的索引
// current_num: 当前构建的数的数值
// current_divisors: 当前构建的数的约数个数
// max_exponent_allowed: 当前质数允许的最大指数
void find_max_divisors(int prime_idx, ll current_num, ll current_divisors, int max_exponent_allowed) {
    // 如果当前数值已经超过限制，则停止
    if (current_num > limit_n) {
        return;
    }

    // 更新全局最优解
    if (current_divisors > max_divisors_count) {
        max_divisors_count = current_divisors;
        result_number = current_num;
    } else if (current_divisors == max_divisors_count && current_num < result_number) {
        result_number = current_num;
    }

    // 如果没有更多质数可用，或者当前数值乘以下一个质数会超过限制，则停止
    if (prime_idx >= primes.size() || (double)current_num * primes[prime_idx] > limit_n) {
        return;
    }

    // 尝试为当前质数设置不同的指数
    ll power_of_prime = 1;
    for (int exponent = 1; exponent <= max_exponent_allowed; ++exponent) {
        // 检查是否会溢出或超过限制
        if ((double)current_num * primes[prime_idx] > limit_n) {
            break;
        }
        current_num *= primes[prime_idx];
        power_of_prime *= primes[prime_idx]; // 记录当前质数的幂次

        // 递归调用，考虑下一个质数，指数必须小于等于当前质数的指数
        find_max_divisors(prime_idx + 1, current_num, current_divisors * (exponent + 1), exponent);
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    sieve(60); // 预计算足够多的质数，因为我们最多需要13个质数

    std::cin >> limit_n;

    // 从第一个质数 (2) 开始搜索，初始约数个数为1，允许的最大指数可以设得比较大
    find_max_divisors(0, 1, 1, 60); // 60 是一个足够大的初始最大指数

    std::cout << result_number << std::endl;

    return 0;
}