反素数 解题报告

解题报告

算法进阶指南 反素数

题意

设 $g(x)$ 为 $x$ 的约数个数,
若对于任意 $1 \le i \le x$, 都有 $g(i)<g(x)$, 则称 $x$ 为反素数.
给出一个正整数 $n$ $(n \le 2000000000)$, 求不大于 $n$ 的最大反素数.

思路

先考虑把一个数质因数分解, 那么这个数的约数个数就是它的每个质因子个数+1 的乘积.

设 $x$ 为我们当前要判断的数, 若存在一个 $y < x$ ,且 $g(y)=g(x)$, 则 $x$ 一定不是反素数.

所以我们可以得到一个结论 :
一个反素数的质因子的指数序列一定是一个非升序列.

原因是: 若它不是一个非升序列, 则我们可以将它从大到小排序, 得到一个非升序列, 这个序列所代表的数比原数小, 且它的约数个数和原数相同, 所以原数不是反素数.

又因为 $\Pi_{i=1}^{10} pri[i] > 2000000000$, 所以我们要求的反素数的质因子个数不会超过 10 个, 直接 dfs 就可以了.

其实按照题目的要求, 只要求出第一个比 $n$ 小的反素数就行了, 但写代码的时候脑抽, 直接把所有反素数求出来然后再 $log$ 查询...

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+7;
const int M=2000+7;
const int inf=0x3f3f3f3f;
const int lim=2000000000;
int n,pri[40],cnt,v[40],num[M],tot,po[40][40];
void pre(){
    for(int i=2;i<=35;i++){
        if(!v[i]){ v[i]=i; pri[++cnt]=i; }
        for(int j=1;j<=cnt;j++){
            if(pri[j]>v[i]||i*pri[j]>35) break;
            v[i*pri[j]]=pri[j];
        }
    }
    for(int i=1;i<=cnt;i++){
        po[i][0]=1; po[i][1]=pri[i];
        int j=1;
        while(po[i][j]<=lim&&po[i][j]>0){ po[i][j+1]=po[i][j]*pri[i]; j++; }
    }
}
void dfs(int k,ll res,int g,int lst){
    if(k>cnt||res>=lim||res<=0) return;
    if(res<num[g]){ tot=max(tot,g); num[g]=res; 
    }
    for(int i=lst;i>=0;i--)
        dfs(k+1,res*po[k][i],g*(i+1),i);
}
int main(){
//  freopen("antiprime.in","r",stdin);
//  freopen("antiprime.out","w",stdout);
    pre();
    memset(num,127,sizeof(num));
    dfs(1,1,1,31);
    for(int i=tot;i>=0;i--) num[i]=min(num[i],num[i+1]);
    tot=unique(num+1,num+1+tot)-num-1;
    cin>>n;
    int t=lower_bound(num+1,num+1+tot,n)-num;
    if(num[t]>n||t>tot) t--;
    printf("%d\n",num[t]);
    return 0;
}