AcWing198.反素数（数学+DFS）xiaodangao

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

如果某个正整数x满足：对于任意的小于x的正整数 i，都有g(x)>g(i) ，则称x为反素数。

例如，整数1，2，4，6等都是反素数。

现在给定一个数N，请求出不超过N的最大的反素数。

输入格式

一个正整数N。

输出格式

一个整数，表示不超过N的最大反素数。

数据范围

$1 \le N \le 2*10^9$

输入样例：

输出样例：

思考这个题的时候，我发现了反素数的一系列质因数必须能分解成 $2^{k1},3^{k2}...$ 形如这种的从最小素数开始且连续且指数 $k1,k2$ 非严格单调递增的，然后；但是当时没有考虑到的一点是从最小素数开始连续的10项素数的乘积已经大于 $2*10^9$ ，并且当时并没有想到搜索，今后不能犯经验主义错误，全面考虑。
思路：发现这一条性质之后，运用dfs枚举每一个质因数的个数；
$Code:$


/*************************************************************************
    > File Name: acwing.cpp
# Author: Badwoman
# mail: 1194446133@qq.com
    > Created Time: 2020年12月20日 星期日 20时32分09秒
 ************************************************************************/

#include<set>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<map>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define bep(i,a,b) for(int i=a;i>=b;--i)
#define lowbit(x) (x&(-x))
using namespace std;
const ll N = 100,inf = 2e9+10;
ll n;
bool st[N*10];
ll prime[N],tot;
void iniv(){
    for(ll i=2;i<=N;++i){
        if(!st[i]){
            prime[++tot] = i;
            for(ll j=i*i;j<=N;j+=i)st[j] = true;
        }
    }
}
ll work[N],ans,mx;
void dfs(ll now,ll x,ll id){
    ll cnt = 0;
    while(cnt < now){x*=prime[id],cnt++;if(x>=inf){now = cnt;break; }  }
    bool flag = true;
    for(ll i=now;i>=1;--i){
        if(x <= n&&prime[id+1]<=31){
        work[id] = i;
        ll sum = 1;dfs(i,x,id+1);
        for(ll k=1;k<=id;++k)sum*=work[k]+1;
        if(sum>mx&&x<=n)ans = x,mx = sum;
        else if(sum==mx&&ans>x)ans = x;
        }
        x /= prime[id] ;
    }
}
void solve(){
    scanf("%lld",&n);
    dfs(31,1,1);
    printf("%lld\n",ans);
}
int main(){
    iniv();
    solve();
    return 0;
}

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。