[TIOJ 1620] LVL格殺

作法：

因為一個數的因數個數成長的速度很慢，所以大概可以猜到這個函數會噴的很快，沒多久就衝過 int 範圍了，所以可以直接把這個數列算出來。但要注意到當數列的數夠大的時候，每個數的因數都會有 7 * 11 * 13 ，因為多乘一個質數可以讓因數個數 * 2，所以到了夠大的數之後就可加剪枝了。

感覺這不是正派作法(廢話?XD)，正常解應該是把所有候選人都列出來再暴力作XD不過感覺蠻麻煩的就沒有想了XD

用來找這個數列的 code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=50000 ;
 
int p[maxn],pcnt=0 ;
bool vis[maxn] ;
 
main()
{
    for(int i=2;i*i<maxn;i++) if(!vis[i])
        for(int j=i*i;j<maxn;j+=i) vis[j]=1 ;
    for(int i=2;i<maxn;i++) if(!vis[i])
        p[++pcnt]=i ;
    int ma=0 ;
//    for(int i=1;i<=2147483646;i++)
    for(int i=61261200;i<=2147483646;i++) if(i%1001==0)
    {
        int x=i , num=1 ;
        for(int j=1;j<=pcnt && x!=1 && p[j]*p[j]<=x && (x>maxn||vis[x]);j++)
            if(x%p[j]==0)
        {
            int d=1 ;
            while(x%p[j]==0) d++ , x/=p[j] ;
            num*=d ;
        }
        if(x!=1) num*=2 ;
        if(num>ma) ma=num , printf("%d\n",i) ;
    }
}

AC code :

#include<bits/stdc++.h>
using namespace std;
int ans[]={0,1,2,4,6,12,24,36,48,60,120,180,240,360,720,
840,1260,1680,2520,5040,7560,10080,15120,20160,25200,27720,
45360,50400,55440,83160,110880,166320,221760,277200,332640,
498960,554400,665280,720720,1081080,1441440,2162160,2882880,
3603600,4324320,6486480,7207200,8648640,10810800,14414400,
17297280,21621600,32432400,36756720,43243200,61261200,73513440,
110270160,122522400,147026880,183783600,245044800,294053760,
367567200,551350800,698377680,735134400,1102701600,1396755360,2095133040} ;
main()
{
    int n ;
    while(scanf("%d",&n)!=EOF) printf("%d\n",ans[n]) ;
}