點擊打開鏈接

1225: [HNOI2001] 求正整數

Time Limit:?10 Sec??Memory Limit:?162 MB
Submit:?835??Solved:?349
[Submit][Status][Discuss]

Description

對于任意輸入的正整數n，請編程求出具有n個不同因子的最小正整數m。例如：n=4，則m=6，因為6有4個不同整數因子1，2，3，6；而且是最小的有4個因子的整數。

Input

n（1≤n≤50000）

Output

m

Sample Input

4

Sample Output

6

1.數據范圍只有50000，計算可得約數的個數最多16個，先打出一張素數表

以后的素數對答案沒有貢獻?


2.dfs(x,y,z);
x表示搜索到的正整數，y表示x的因子個數，z表示已經搜索到了第z個質數


3.這樣會超時，考慮剪枝
1.枚舉當前質數的指數i時，y%(i+1)==0,那么就是求 y的因子數，
時間復雜度為sqrt(y);
2.當前質數的指數不可以為0，因為是從小到大搜索，還是比較有用
4.x是會爆long long的（比賽時用double卡的精度）如果搜索時加高精度就太麻煩了，
考慮用對數。log(n)=Σa[i]*log(pri[i])?
5.在<float.h>中定義了浮點類型的范圍：
#define DBL_MAX? ? ? ? ?1.7976931348623158e+308?
// max value?
#define DBL_MIN? ? ? ? ?2.2250738585072014e-308
//min positive value

#include<iostream> #include<cstring> #include<cfloat> #include<cstdio> #include<cmath> using namespace std; int n,ans[100005],res[21],tmp[21],pri[]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53}; double mn=DBL_MAX,lg[21]; void print() {ans[0]=ans[1]=1;for(int i=1;i<=16;i++){for(;res[i]>0;res[i]--){for(int j=1;j<=ans[0];j++)ans[j]*=pri[i];for(int j=1;j<=ans[0];j++)ans[j+1]+=ans[j]/10,ans[j]%=10;if(ans[ans[0]+1]!=0)ans[0]++;while(ans[ans[0]]/10!=0)ans[ans[0]+1]+=ans[ans[0]]/10,ans[ans[0]]%=10,++ans[0];}}for(int i=ans[0];i>=1;i--)printf("%d",ans[i]);printf("\n"); } void dfs(double x,int y,int z)//現在的數是e^x，還剩y個因子，選到第z個質數 {if(x>=mn)return ;if(y==1){mn=x;memset(res,0,sizeof(res));for(int i=1;i<=z-1;i++)res[i]=tmp[i];return ;}if(z>16)return ;for(int i=0;(i+1)*(i+1)<=y;i++)//找y的因子 if(y%(i+1)==0){if(i!=0){tmp[z]=i;dfs(x+lg[z]*i,y/(i+1),z+1);}if((i+1)*(i+1)!=y){tmp[z]=y/(i+1)-1;dfs(x+lg[z]*(y/(i+1)-1),i+1,z+1);}} } int main() {scanf("%d",&n);for(int i=1;i<=16;i++)lg[i]=log(pri[i]);dfs(0,n,1);print();return 0; } 與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的bzoj 1225 暴搜动态规划的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。