[题解]（约数）BZOJ_1053

三条引理：
1.1~N中最大的反质数，就是1~N中约数个数最多的最小的一个

比较显然，是应该看出来的一条

2.1~N中任何数的不同因子都不会超过10个，且所有质因子的指数之和不超过30：

2*3*5*7*11*13*17*19*23*29*31 > 2*10^9

2^30 > 2*10^9

3.x的质因子是连续的若干最小的质数，质数单调递减

如果有指数不单调，那么可以通过交换质因子的方式证出不是反质数或者更优

通过搜索实现：

枚举每个质因子的指数，根据引理1更新答案，根据引理2、3剪一些枝

不开longlong一时爽，一会提交火葬场

#include<bits/stdc++.h>

#define ll long long

using namespace std;

int n;

const int p[]={,,,,,,,,,,};

int ans,numans;//数和约数个数

void dfs(int pos,ll sum,int lst,int sumk,int cnt){//sumk指数之和，cnt为约数个数

    if(sumk>)return;

    if(pos==){

        if(cnt>numans)ans=sum,numans=cnt;

        else if(cnt==numans&&sum<=ans)ans=sum,numans=cnt;

        return;

    }

    int s=;

    for(int i=;i<=lst;i++){

        dfs(pos+,sum*s,i,sumk+i,cnt*(i+));

        s*=p[pos];

        if((long long)(sum*s)>n)break;

    }

}

int main(){

    scanf("%d",&n);

    dfs(,,,,);

    printf("%d",ans);

}

巴特西

[题解]（约数）BZOJ_1053_反素数

最新文章

热门文章