【BZOJ 1053】[HAOI2007]反素数ant

【链接】我是链接,点我呀:)
【题意】

在这里输入题意

【题解】

用小的质数去凑那个数字。
显然比用大质数去凑划算。
因为
对于\(x = p1^{q1}*p2^{q2}*...*pn^{qn}\)
x的因子个数等于(q1+1）(q2+1)....(qn+1);
显然 你用的质数越小。
这个指数就能更大一点。
(表示相同的数字的情况下。至少不会更差。

根据这个。
又有235....2329>2*10^9
则只要考虑这10个质数就可以了。
枚举它们用了多少个。
(即枚举各个质数的指数
(找出最优解就好。

【代码】

#include <bits/stdc++.h>
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define all(x) x.begin(),x.end()
#define pb push_back
#define ls l,mid,rt<<1
#define rs mid+1,r,rt<<1
using namespace std;

const double pi = acos(-1);
const int dx[4] = {0,0,1,-1};
const int dy[4] = {1,-1,0,0};
const int a[11] = {1,2,3,5,7,11,13,17,19,23,29};

LL n;
LL ansnum=-1,ansyueshu;

void dfs(LL cur,LL idx,LL cnt,LL yueshu){
    if (idx>10) return;
    //超过范围结束。

    //cur大于n了,那么结束
    if (cur>n) return;
    if (ansnum==-1){
        ansnum = cur;
        ansyueshu = yueshu;
    }else{
        if (yueshu>ansyueshu){
            ansnum = cur;
            ansyueshu = yueshu;
        }else if (yueshu==ansyueshu){
            if (cur<ansnum){
                ansnum = cur;
                ansyueshu = yueshu;
            }
        }
    }

    //还是选择这个数字继续乘。
    dfs(cur*a[idx],idx,cnt+1,yueshu/(cnt+1)*(cnt+2));

    //选择下一个数字乘。
    dfs(cur,idx+1,0,yueshu);
}

int main(){
    #ifdef LOCAL_DEFINE
        freopen("rush_in.txt", "r", stdin);
    #endif
    scanf("%lld",&n);
    //当前数字,当前选择的是第几个数字,这个数字乘了几次,约数个数
    dfs(1,1,0,1);
    printf("%lld\n",ansnum);
    return 0;
}