#P3085. 反质数加强版SAPGAP

    ID: 2240 传统题 1000ms 512MiB 尝试: 499 已通过: 91 难度: 8 上传者: 标签>CF2400提高+/省选-深度优先搜索可行性剪枝支配关系约数个数乘积公式高精度乘法

反质数加强版SAPGAP

题目描述

先解释一下 SAPGAP = Super AntiPrime, Greatest AntiPrime(真不是网络流),于是你就应该知道本题是一个关于反质数(Antiprime)的问题。下面给出反质数的定义:

将一个正整数 ii 的约数个数记为 g(i)g(i),如 g(1)=1g(1)=1,g(2)=2g(2)=2,g(6)=4g(6)=4。

如果对于一个正整数 kk,对于任意正整数 i<ki<k,均有 g(k)>g(i)g(k)>g(i),则 kk 被称为反质数。

比如说 1,2,4,6,121,2,4,6,12 就是前 55 个反质数。

现在给定一个 nn,求 nn 以内最大的反质数。

你一定会认为这道题很简单,你曾经做过好多遍(它就是许许多多竞赛的原题呀),但是这次真的不一样。

输入格式

一个正整数 nn。

输出格式

一个正整数,表示不超过 nn 的最大的反质数。

1000
840

数据规模与约定

对于 5%5\% 的数据,n≤104n\le 10^4。

对于 10%10\% 的数据,n≤105n\le 10^5。

对于 20%20\% 的数据,n≤109n\le 10^9。

对于 35%35\% 的数据,n≤1017n\le 10^{17}。

对于 60%60\% 的数据,n≤1030n\le 10^{30}。

对于 100%100\% 的数据,1≤n≤101001\le n\le 10^{100}。