poj 3604 Professor Ben

　　继续分解质因数....我想知道那些不到1000ms的代码是怎样写出来的？？我的运行了2641ms才过的...
View Code
 1   #include <cstdio>
 2   #include <cstring>
 3   #include <cstdlib>
 4   #include <cmath>
 5   #include <algorithm>
 6   #include <iostream>
 7 
 8   #define debug 0
 9 
10   using namespace std;
11 
12   typedef long long ll;
13   const int maxn = 5000001;
14 
15   bool np[maxn];
16   ll pn, pr[maxn >> 2];
17 
18   void gp(){
19       memset(np, 0, sizeof(np));
20       np[0] = np[1] = true;
21       pn = 0;
22       for (ll i = 2; i < maxn; i++){
23           if (!np[i]) pr[pn++] = i;
24           for (int j = 0; j < pn && pr[j] * i < maxn; j++){
25               np[pr[j] * i] = true;
26               if (i % pr[j] == 0) break;
27           }
28       }
29       #if debug
30       cout << "pn  " << pn << endl;
31       #endif
32   }
33 
34   void fac(ll a, int *f, int &cnt){
35       int i = 0;
36 
37       cnt = 0;
38       while (pr[i] * pr[i] <= a && i < pn){
39           while (a % pr[i] == 0){
40               f[cnt++] = pr[i];
41               a /= pr[i];
42           }
43           i++;
44       }
45       if (a != 1) f[cnt++] = a;
46   }
47 
48   void deal(ll a){
49       int f[50], tmp;
50       int ans = 1;
51       int cnt = 0;
52       int n = 0;
53 
54       if (!np[a]) {
55         printf("9\n");
56         return ;
57       }
58       memset(f, 0, sizeof(f));
59       fac(a, f, n);
60       sort(f, f + n);
61       #if debug
62       cout << "n  " << n << endl;
63       for (int i = 0; i < n; i++){
64           cout << f[i] << endl;
65       }
66       f[n] = 0;
67       #endif
68       for (int i = 0; i < n; i++){
69           cnt++;
70           if (f[i] != f[i + 1]) {
71               #if debug
72               cout << "cnt " << cnt << endl;
73               #endif
74               tmp = (cnt + 1) * (cnt + 2) >> 1;
75               tmp *= tmp;
76               ans *= tmp;
77               cnt = 0;
78           }
79           if (!ans) break;
80       }
81       printf("%d\n", ans);
82   }
83 
84   int main(){
85       int a, n;
86 
87       gp();
88       scanf("%d", &n);
89       while (n-- && ~scanf("%d", &a)){
90           deal(a);
91       }
92 
93       return 0;
94   }
——written by Lyon