高精度+搜索+质数 BZOJ1225 [HNOI2001] 求正整数

 1 // 高精度+搜索+质数 BZOJ1225 [HNOI2001] 求正整数
 2 // 思路：
 3 // http://blog.csdn.net/huzecong/article/details/8478689
 4 // M=p1^(t1)*p2^(t2)*p3^(t3)....
 5 // N=(t1+1)*(t2+1)*(t3+1)*(t4+1)...
 6 // 所以t最大到16，就可以暴力搜索了
 7 
 8 
 9 #include <bits/stdc++.h>
10 using namespace std;
11 #define LL long long
12 const double inf = 123456789012345.0;
13 const LL MOD =100000000LL; 
14 const int N =1e5+10; 
15 #define clc(a,b) memset(a,b,sizeof(a))
16 const double eps = 1e-7;
17 void fre(){freopen("in.txt","r",stdin);}
18 void freout() {freopen("out.txt","w",stdout);}
19 inline int read() {int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}return x*f;}
20 
21 int n;
22 const int M=16;
23 const int p[16]= {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47}; 
24 double Log[16];
25 class bignum  {  
26     public:  
27         LL num[N];  
28         int tot;  
29         bignum() {}  
30         bignum(LL x) {  
31             clear();  
32             while (x) num[tot++] = x % MOD, x /= MOD;  
33         }  
34         void clear(){  
35             tot = 0;  
36             for (int i = 0; i < N; ++i) num[i] = 0LL;  
37         } 
38         void operator *= (const int &x){  
39             for (int i = 0; i < tot; ++i) num[i] *= x;  
40             for (int i = 0; i < tot; ++i)  
41                 if (num[i] >= MOD) {  
42                     num[i + 1] += num[i] / MOD;  
43                     num[i] %= MOD;  
44                 }  
45             while (num[tot]) {  
46                 if (num[tot] >= MOD) {  
47                     num[tot + 1] += num[tot] / MOD;  
48                     num[tot] %= MOD;  
49                 }  
50                 ++tot;  
51             }  
52         }  
53         void print()  {  
54             printf("%lld", num[tot - 1]);  
55             for (int i = tot - 2; i >= 0; --i)  
56             printf("%08lld", num[i]);  
57         }  
58 }ans(1);  
59 
60 int t[16],ct[16];
61 double mn;
62 int cnt;
63 
64 void dfs(int d,int x,int m,double tem){
65     if(tem>mn) return;
66     if(x==1){
67         if(tem<mn){
68             mn=tem,cnt=d-1;
69             for(int i=1;i<d;i++) t[i]=ct[i];
70         }
71     }
72     for(int i=1;i*i<=x&&i<=m;i++){
73         if(!(x%i)){
74             if(i!=1){
75                 ct[d]=i;
76                 dfs(d+1,x/i,i,tem+(double)Log[d]*(i-1));
77             }
78             if(x/i<=m&&x/i!=i){
79                 ct[d]=x/i;
80                 dfs(d+1,i,x/i,tem+(double)Log[d]*(x/i-1));
81             }
82         }
83     }
84 }
85 
86 int main(){
87     scanf("%d",&n);
88     for(int i=1;i<=15;i++) Log[i]=(double)log(p[i]);
89     mn=inf;
90     cnt=0;
91     dfs(1,n,n,0.0);
92     for(int i=1;i<=cnt;i++){
93         for(int j=t[i]-1;j>0;j--){
94             ans*=p[i];
95         }
96     }
97     ans.print();
98     return 0;
99 }