[HAOI2007]反素数

[HAOI2007]反素数

题目描述

对于任何正整数x，其约数的个数记作$gleft ( x ight )$。例如$gleft ( 1 ight )=1,gleft ( 6 ight )=4$。

如果某个正整数x满足：$0 lt i lt x$，都有$gleft ( x ight )>gleft ( i ight )$，则称为反质数。例如，整数$1,2,3,4$等都是反质数。

现在给定一个数N，你能求出不超过N的最大的反质数么？

输入格式

一个数N。

输出格式

不超过N的最大的反质数。

输入输出样例

输入 

1000

输出

840

说明/提示

$1leq Nleq 2 imes 10^{9}$

---

sol:

这题需要知道几个性质。

$1.$ 我们要找的答案就是$[1,N]$里面约数个数最多同时尽可能小的数

$2.$
$[1,N]$中任何的不同质因子都不会超过$10$个，且所有质因子的指数总和不超过$30$。

证明：
最小的 $ 11 $个质数的积

$2 imes 3 imes 5 imes 7 imes 11 imes 13 imes 17 imes 19 imes 23 imes 29 imes 31＞2 imes 10^9$

所以,$Nleq 2 imes 10^9$不可能有多于$10$个不同的质因子。
即使只包含最小的质数$2$，仍然有$2^{31}gt 2 imes 10^9$所以$ Nleq 2 imes 10^9$的质因子不会超过$30$个。

$3.$

$ {forall}x in [1,N] $

$ x $为反质数的必要条件是:$x$分解质因数后可写作$2^{c_1} imes 3^{c_2} imes ldotsldots imes 29^{c_{10}}$,并且$c_1geq c_2geq c_3geq ldotsldotsgeq c_{10}geq 0$。
通俗的讲，$x$的质因子是连续的若干个最小的质数，并且质数单调递增。

所以我们可以用搜索算法来搜出每一个质数的指数就$OK$了

code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,p[11]= {0,2,3,5,7,11,13,17,19,23,29},ans=INT_MAX,total;
void dfs(ll k,ll num,ll fir_sum,ll now_sum) {
    if(num>n)
        return;
    if(k==11) {
        if(now_sum>total) {
            total=now_sum;
            ans=num;
        }
        if(now_sum==total)
            ans=min(ans,num);
        return;
    }
    for(ll i=fir_sum; i>=0; i--) {
        ll t=1;
        for(ll j=1; j<=i; j++)
            t*=p[k];
        if(t>n) continue;
        dfs(k+1,num*t,i,now_sum*(i+1));
    }
}
int main() {
    scanf("%lld",&n);
    dfs(1,1,30,1);
    printf("%lld
",ans);
    return 0;
}