BZOJ 1053-反素数

[mathjax]
题目：

对于任何正整数x，其约数的个数记作\(g(x)\)。例如\(g(1)=1\)、\(g(6)=4\)。如果某个正整数x满足：\(g(x)>g(i)\) \(（0<i<x）\)，则称x为反质数。例如，整数 \(1，2，4，6\)等都是反质数。现在给定一个数 \(N（1<=N<=2*10^9）\)，求出不超过N的最大的反质数.

思路：
引理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^{31}>2*10^9)\)
引理3：x为反质数的必要条件是，x可写作\(2^{c_1}*3^{c_2}*5^{c_3}*7^{c_4}*11^{c_5}*13^{c_6}*17^{c_7}*19^{c_8}*23^{c9}*29^{c{10}}\),并且\(c_1>=c2>…>=c{10}>=0\) (由反证法可得)
综上，可通过dfs求出各个\(c_1,c_2…c_n\) ,搜索过程中根据上述限制要求进行剪枝。
约数个数为\((c_1+1)*(c_2+1)*…*(cn+1)=\prod{i=1}^{n}(c_i+1)\) .
由引理1确定最后结果。

代码：

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>

using namespace std;
#define MAX_N 2e9

typedef  long long ll;
typedef  unsigned long long ull;

int prime[12]={2,3,5,7,11,13,17,19,23,29,31};
ll ans;
ll acnt;
ll n;

void dfs(ll x,ll cnt,int step){
    if(step==11){
       if((x>ans&&cnt>acnt)||x<=ans&&cnt>=acnt){
          acnt=cnt;
          ans=x;
       }
       return ;
    }
    ll P=1;
    for(int i=0;i<31;i++){
      if(x*P>n) break;
      dfs(x*P,cnt*(i+1),step+1);
      P*=prime[step];
    }
}

int main() {
  cin>>n;
  dfs(1,1,0);
  printf("%d\n",ans);
  return 0;
}