URAL1748. The Most Complex Number

反素数
素数的个数随大小的递增而递减可以相同
注意各种超啊
 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<stdlib.h>
 6 #include<cmath>
 7 using namespace std;
 8 #define INF 1e19
 9 #define LL unsigned long long
10 #define N 32000
11 int p[N],f[N],g,po[N];
12 LL maxz,tt,pp[N][100],n;
13 void init()
14 {
15     int i,j;
16 
17     for(i = 2; i < N ; i++)
18     if(!f[i])
19     {
20         for(j = i+i ; j < N ; j+=i)
21         f[j] = 1;
22     }
23     for(i = 2; i < N ; i++)
24     if(!f[i])
25     p[++g] = i;
26     for(i = 1; i <= g ; i++)
27     {
28         pp[p[i]][1] = p[i];
29         for(j = 2 ; ; j++)
30         {
31             double ss = (double)pp[p[i]][j-1]*p[i];
32             if(ss>INF) break;
33             pp[p[i]][j]=ss;
34             //cout<<ss<<endl;
35 
36         }
37         po[i] = j-1;
38     }
39 }
40 void dfs(LL s,int k,int o,LL sum)
41 {
42     int i;
43     LL ts =s;
44     if(o>15) return ;
45     if(maxz<sum||(maxz==sum&&tt>s))
46     {
47         maxz = sum;
48         tt = s;
49     }
50     for(i = 1; i <= min(k,po[o]) ; i++)
51     {
52         if(n/s<pp[p[o]][i]) break;
53         s*=pp[p[o]][i];
54         dfs(s,i,o+1,sum*(LL)(i+1));
55         s = ts;
56     }
57 }
58 int main()
59 {
60     int t,i;
61     init();
62     cin>>t;
63     while(t--)
64     {
65         cin>>n;
66         maxz=1,tt=1;
67         for(i = 1; i < po[2] ; i++)
68         {
69             LL s = pp[2][i];
70             if(s>n)
71             {
72                 if(i>maxz)
73                 {
74                     maxz = i;
75                     tt = pp[2][i-1];
76                 }
77                 break;
78             }
79             dfs(s,i,2,i+1);
80         }
81         cout<<tt<<" "<<maxz<<endl;
82     }
83     return 0;
84 }
View Code