【模板】【数学】反质数

题目链接：https://www.luogu.com.cn/problem/P1463

其实反质数就是要约数最大，在此前提下这个数最小。

然后它分解出来的质数一定是连续的，并且分解出来的质数的指数是单调递减的，所以可以dfs求。

参考：https://blog.csdn.net/qq_40942372/article/details/82016727

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll p[20] = { 0 , 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47};
ll n,best,ans;
void dfs(int dep,ll now,ll num,int limit){
    if(dep >= 16) return;
    if( now > n) return;
    if( num > best ){
        best = num;
        ans = now;
    }
    if( num == best && ans > now ) ans = now;
    for(int i = 1;i<=limit;++i){
        now *= p[dep];
        if( now > n) return;
        dfs( dep + 1,now,num*(i+1),i);
    }
}
int main(){
    scanf("%lld",&n);
    best = 0;
    dfs(1,1,1,35);
    printf("%lld",ans);
}