反素数 Antiprime

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 865 字

给定n，求不大于n的最大反素数

一本通
例

正文

/*
原题：T1625「一本通 6.3 例 1」反素数 Antiprime
题意：给定 n，求不大于 n 的最大反素数（反素数 = 约数个数严格多于所有更小数的数，等价于此范围内约数最多且最小者）。
思路：DFS 枚举素数 2,3,5,...,23 的幂，要求指数非递增；对每个合数记录约数个数，维护最大值及对应最小数值。
复杂度：时间 O(可枚举状态数，极小) / 空间 O(1)
易错点：指数必须非递增以保证不重不漏；答案为约数最多且数值最小者。
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int P[9]={2,3,5,7,11,13,17,19,23};
ll N, best;
int maxd;
// idx:当前考虑第几个素数；lastExp:上一个素数的指数上限；val:当前乘积；div:当前约数个数
void dfs(int idx, int lastExp, ll val, int div){
    if(div>maxd || (div==maxd && val<best)){
        maxd=div;
        best=val;
    }
    if(idx==9) return;
    ll p=P[idx];
    ll pw=p;
    for(int e=1;e<=lastExp;e++){
        if(val>N/pw) break;
        dfs(idx+1, e, val*pw, div*(e+1));
        if(pw>N/p) break;
        pw*=p;
    }
}
int main(){
    cin>>N;
    maxd=0;
    best=0;
    dfs(0, 30, 1, 1);
    cout<<best<<"\n";
    return 0;
}

反素数 Antiprime

正文

一本通·提高篇的其它内容