[BZOJ 1053][HAOI2007]反素數ant

[BZOJ 1053][HAOI2007]反素數ant

這個題很有意思，雖然代碼很短，但是思路非常巧妙。

首先這個題問不超過N的最大的x，使得任何比x小的數的約數個數都比x的約數個數少。其實說到底就是求[1,n]中約數個數最多的數，如果有多個這樣的數，取最小的（因為題目要求任何比x小的數的約數個數都必須小於x的約數個數，不能取等）。另外做這題之前還要掌握約數個數公式：若把x表示成多個質因數的乘積，x=p1^a1*p2^a2*...pn^an，p1,p2...pn是質數，那麼x的約數個數=(a1+1)*(a2+1)*...(an+1)。我們可以直接DFS暴搜找答案，枚舉每一個質因數的冪，然後根據已經乘積得出的數的約數個數，不斷更新答案。另外此題有個小技巧需要注意：枚舉的質因數只要是從小到大前10個質數就可以了，因為從小到大前十個以上的質數的乘積已經超出了n的最大范圍。而且枚舉第i個質因數的冪時，第i個質因數的冪大小不會超過第i-1個質因數的冪。（因為差不多大小的數字，大的質因數的指數比小的質因數的指數大的數字絕對沒有小的質因數的指數比大的質因數指數大的數字的約數個數多，根據貪心思想，大的質因數會占用更大的積，不如小的質因數來得劃算）

#include 
#include 
#include 
#include 
#include 

#define INF 0x3f3f3f3f

using namespace std;

typedef long long int LL;

int primes[]={0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29}; //質數打表

LL n,ans,cnt; //cnt=約數個數最大值,ans=約數個數取最大值時的最小的數字

void DFS(LL num,LL maxP,int now,int nowcnt) //num=當前乘積得到的數，maxp=下一個質數最大的冪，now=當前狀態下使用的質數下標，nowcnt=當前數約數個數
{
    if(nowcnt>cnt||nowcnt==cnt&&num10) return; //取的質數個數太多了，已經超出了n的范圍，不必繼續搜索了
    LL nownum=num;
    for(int i=1;i<=maxP;i++) //枚舉下一個質因數的冪
    {
        nownum*=(LL)primes[now];
        if(nownum>n) return;
        DFS(nownum,i,now+1,nowcnt*(i+1));
    }
}

int main()
{
    scanf(%lld,&n);
    ans=1,cnt=1;
    DFS(1,INF,1,1);
    printf(%lld
,ans);
    return 0;
}