POJ 1840 - Eqs

http://poj.org/problem?id=1840

概要

係数 a1, ..., a5 が与えられる． a1 * x1^3 + ... + a5 * x5^3 = 0 を満たすような (x1, ..., x5) の組み合わせの数を答える．

ただし xi は xi ∈ [-50, 50], xi != 0 なる整数．

制約

• -50 <= ai <= 50

解法

a1*x1^3 + a2*x2^3 のとりうる値 S1 と，a3*x3^3 + a4*x4^3 + a5*x5^3 のとりうる値 S2 をすべて生成し，S1 の各値が S2 に含まれている数を合計する． HashMap で数えるのがたぶん一番早いが，配列をソートして二分探索でも十分間に合った (1063MS)．

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 int main()
 6 {
 7   int a[5];
 8   for (int i = 0; i < 5; i++) {
 9     scanf("%d", &a[i]);
10   }
11 
12   static const int M = 100;
13   static int x2[M*M], x3[M*M*M];
14   int x2_size = 0, x3_size = 0;
15   for (int i = -50; i <= 50; i++) {
16     if (i == 0) {
17       continue;
18     }
19     const int x = i*i*i;
20     for (int j = -50; j <= 50; j++) {
21       if (j == 0) {
22         continue;
23       }
24       const int y = j*j*j;
25       x2[x2_size++] = a[0]*x + a[1]*y;
26       for (int k = -50; k <= 50; k++) {
27         if (k == 0) {
28           continue;
29         }
30         const int z = k*k*k;
31         x3[x3_size++] = a[2]*x + a[3]*y + a[4]*z;
32       }
33     }
34   }
35   sort(x2, x2+x2_size);
36   sort(x3, x3+x3_size);
37 
38   int c = 0;
39   for (int i = 0; i < x2_size; i++) {
40     const pair<int*, int*> p = equal_range(x3, x3+x3_size, x2[i]);
41     c += distance(p.first, p.second);
42   }
43   printf("%d\n", c);
44   return 0;
45 }