Description

对于任何正整数 \(x\), 其约数的个数记作 \(g(x)\). 例如 \(g(1) = 1, g(6) = 4\). 如果某个 正整数 \(x\) 满足:\(g(x) > g(i) (\forall\ 0 \lt i \lt x)\), 则称 \(x\) 为反质数. 例如, 整数 \(1, 2, 4, 6\) 等都是反质数. 现在给定一个数 \(n\), 你能求出不超过 \(n\) 的最大的反质数么?

Input

一个数 \(n (1 \leq n \leq 2 \times 10^9)\).

Output

不超过 \(n\) 的最大的反质数.

Sample Input

1000

Sample Output

840

Explanation

考虑到如果想让约束尽量地大, 也就是说应该让所有质因数都尽量地小对吧...... 具体证明 (很不严谨, 但大概看看可以意会) 如下:

\[\because x = \sum_{i=1}^{k} p_i^{t_i}\]

\[\therefore g(x) = \sum_{i=1}^{k} t_i + 1\]

但是我们并不需要把所有的 \(x\) 都求出来对不对 (比如质数). ...... 所以我们只需要把那些 潜在的 \(g(x)\) 大的值求出来就可以了. 这个可以直接上爆搜, 然后记一下前 \(12\) 个质数再跑一边 dfs 确认一下就好了.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;
const int primes[13] = {0,
    2,  3,  5,  7,  11,
    13, 17, 19, 23, 29,
    31, 37};

int n;
lli final_prd = 1,
    final_cnt = 1;

void work_dfs(
        int pos, // Position in primes[] array
        lli cur_val, // Current product of prime factors
        lli cnt, // All factors of cur_val
        int last_cnt) // Upper bound of next cnt
{
    if (pos == 12) {
        if ((cur_val > final_prd && cnt > final_cnt)
                || (cur_val <= final_prd && cnt >= final_cnt))
            final_prd = cur_val,
            final_cnt = cnt;
        return ;
    }
    int prm_dup = 1; // Duplications of primes[pos]
    for (int i = 0; i <= last_cnt; i++) {
        work_dfs(pos + 1, cur_val * prm_dup, cnt * (i + 1), i);
        prm_dup *= primes[pos];
        if (cur_val * prm_dup > n)
            break;
    }
    return ;
}

int main(int argc, char** argv)
{
    scanf("%lld", &n);
    work_dfs(1, 1, 1, 20); // 2^20 is sufficient.
    printf("%lld\n", final_prd);
    return 0;
}