bzoj1053[HAOI2007]反素數ant

題目大意：給定一個正整數n，讓你求出[1,n]内質因數個數最多的數，且該數越小越好。比如8以内，6和8都有4個因數，但6更優。

範圍：n<=2*10^9

做法：dfs

拿到這種題目的時候，看到數論的東西（好吧其實這不算=w=）第一反應就是要推些什麼東西出來。我們知道一個數的質因數個數是由他的質因子決定的。一個數必然能夠拆分成以下的樣子：n=(a1^b1)*(a2^b2)*(a3^b3)...*(ai^bi)。其中a數組表示不同的質數，b數組表示該質數在n中的數量。不難發現，n的因子個數為1*(b1+1)*(b2+1)*(b3+1)...(bi+1)。那麼我們還能發現一個性質，就是當a數組中的數依次遞增時，即a1<a2<a3...時，b1>=b2>=b3...。為什麼呢？很顯然當兩個質數的次方數不同時，我們讓小的質數擁有更多的次方數，這樣他們的因子數量的大小不變，但是他們總的積卻更小

有了這兩個性質我們就可以開始搜尋了。我們發現2*10^9<2*3*5*7*11*13*19*23*29，這說明我們最多隻需要把a數組枚舉到9就可以了。

program bzoj1053;

  var

    i,j,k,l,m,n:longint;

    f:array[1..10] of longint;

    max1,max2:longint;

  procedure dfs(ans,num,sum,lnum:int64);//num表示目前枚舉到第幾個質數,sum表示目前所有質數的乘積,lnum表示上一個質數有多少個,ans表示目前有幾個因子。

    var

      i:longint;

    begin

      if ans>max1 then begin max1:=ans; max2:=sum; end;

      if (ans=max1)and(max2>sum) then max2:=sum;

      for i:=1 to lnum do

        begin

          if sum*f[num]>n then break;//如果目前數的乘積已經超過了n那麼就退出

          sum:=sum*f[num];

          dfs(ans*(lnum+1),num+1,sum,i);

        end;

    end;

  begin

    f[1]:=2; f[2]:=3; f[3]:=5; f[4]:=7; f[5]:=11;

    f[6]:=13; f[7]:=17; f[8]:=19; f[9]:=23; f[10]:=29;

    readln(n);

    max1:=0;

    dfs(1,1,1,1000);

    writeln(max2);

  end.