poj1840Eqs【散列表】

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 using namespace std;
 6 
 7 const int mod = 100007;
 8 
 9 struct Node {
10     int d;
11     Node* next;
12 };
13 
14 Node* head[mod + 10];
15 Node nd[mod + 10];
16 
17 int main() {
18     int a, b, c, d, e;
19     while(EOF != scanf("%d %d %d %d %d",&a, &b, &c, &d, &e) ) {
20         memset(head, 0, sizeof(head));
21         int n_cnt = 0;
22         for(int i = -50; i <= 50; i++) {
23             for(int j = -50; j <= 50; j++) {
24                 if(i == 0 || j == 0) continue;
25                 int num = a * i * i * i + b *j * j * j;
26                 int xx = num > 0 ? num : -num;
27                 int p = xx % mod;
28                 Node*pt = head[p];
29                 while(pt) {
30                     pt = pt -> next;
31                 }
32                 nd[n_cnt].d = num;
33                 nd[n_cnt].next = head[p];
34                 head[p] = &nd[n_cnt++];
35             }
36         }
37         int ans = 0;
38         for(int i = -50; i <= 50; i++) {
39             for(int j = -50; j <= 50; j++) {
40                 for(int k = -50; k <= 50; k++) {
41                     if(i == 0 || j == 0 || k == 0) continue;
42                     int num = c * i * i * i + d * j * j * j + e * k * k * k;
43                     num = - num;
44                     int xx = num > 0 ? num : - num;
45                     int p = xx % mod;
46                     Node * pt = head[p];
47                     while(pt) {
48                         if(pt -> d == num) ans++;
49                         pt = pt -> next;
50                     }
51                 }
52             }
53         }
54         printf("%d\n", ans);
55     }
56     return 0;
57 }

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 const int mod = 10007;
 7 
 8 struct Node {
 9     int to;
10     int next;
11 }e[mod + 10];
12 
13 int head[mod + 10];
14 
15 int tot;
16 void add(int u, int v) {
17     e[tot].to = v;
18     e[tot].next = head[u];
19     head[u] = tot++;
20 }
21 
22 int Find(int p, int num) {
23     int cnt = 0;
24     for(int i = head[p]; i; i = e[i].next) {
25         if(e[i].to == num) cnt++;
26     }
27     return cnt;
28 }
29 
30 int Fabs(int x) {
31     return x > 0 ? x : - x;
32 }
33 
34 int main() {
35     int a, b, c, d, e;
36     while(EOF != scanf("%d %d %d %d %d",&a, &b, &c, &d, &e) ) {
37         memset(head, 0, sizeof(head));
38         tot = 1;
39         for(int i = -50; i <= 50; i++) {
40             for(int j = -50; j <= 50; j++) {
41                 if(i == 0 || j == 0) continue;
42                 int num = a * i * i * i + b * j * j * j;
43                 int p = Fabs(num) % mod;
44                 add(p, num);
45             }
46         }
47         int ans = 0;
48         for(int i = -50; i <= 50; i++) {
49             for(int j = -50; j <= 50; j++) {
50                 for(int k = -50; k <= 50; k++) {
51                     if(i == 0 || j == 0 || k == 0) continue;
52                     int num = c * i * i * i + d * j * j * j + e * k * k * k;
53                     num = - num;
54                     int p = Fabs(num) % mod;
55                     ans += Find(p, num);
56                 }
57             }
58         }
59         printf("%d\n",ans);
60     }
61     return 0;
62 }