BZOJ 1053 [HAOI2007]反素數ant（約數個數）

【題目連結】 http://www.lydsy.com/JudgeOnline/problem.php?id=1053

【題目大意】

　　于任何正整數x，其約數的個數記作g(x)。例如g(1)=1、g(6)=4。

　　如果某個正整數x滿足：g(x)>g(i) 0<i<x，則稱x為反質數。

　　求不超過N的最大的反質數

【題解】

　　此題需要用到結論：

　　　　1.一個數約數個數=所有素因子的次數+1的乘積

　　　　2.小素數多一定比大素數多優。

　　是以預處理出小素數表，利用搜尋解決這個問題

【代碼】

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
int n,ans=1,num=1;
int p[15]={1,2,3,5,7,11,13,17,19,23,29,31};
void dfs(int k,LL nx,int cnt,int len){
    if(k==12){if(nx>ans&&cnt>num||nx<=ans&&cnt>=num){ans=nx;num=cnt;}return;}
    int t=1;
    for(int i=0;i<=len;i++){
        dfs(k+1,nx*t,cnt*(i+1),i);
        t*=p[k];
        if(nx*t>n)break;
    }
}
int main(){
    scanf("%d",&n);
    dfs(1,1,1,20);
    printf("%d\n",ans);
    return 0;
}
           

轉載于:https://www.cnblogs.com/forever97/p/bzoj1053.html