Description
Input
Output
Sample Input
Sample Output
题解：
a1*x13+a2*x23+a3*x33+a4*x43+a5*x53 = 0
<==> a1*x13+a2*x23+a3*x33 = -1*(a4*x43+a5*x53)
可以想办法利用三重循环枚举x1，x2，x3，算出a1*x1^3+a2*x2^3+a3*x^3得到的所有的100*100*100个值，先储存起来，假设存在a[ ]数组里。然后利用两重循环枚举x4，x5，逐个算出-1*(a4*x4^3+a5*x5^3)的所有值，如果这个值也存在于a[ ]中，就代表找到一组可行解，答案+1。
现在的问题就变成了如何快速的查找a[ ]中的值，如果从头到尾扫一遍，那时间复杂度和直接五重循环枚举没有什么区别。
这个问题可以用哈希表优化，先不解释哈希表是什么。先考虑如下问题：
如果要存储和查找线性表(1，75，324，43，1353，90，46)，有两种基本的思路：一种是定义一个数组A[10]，把它们依次存入，但是这会给查找操作带来O(n)的时间复杂度，当数字非常多时，效率也许不可接受；第二种方法是定义数组A[2000]，把这几个数字作为下标，即A[1]=1，A[75]=1，A[324]=1，A[43]=1，A[1353]=1，A[90]=1，A[46]=1，这样查找有没有x时只需判断A[x]是否等于1就可以了时间复杂度O(1)，但是这种方法的问题也很大，就是空间浪费多，空间复杂度高。
现在考虑优化第二种方法，假设我们设计函数h(x) = x mod 1235789 ，把原来的A[x]=1的操作变成A[ h(x) ] = 1 ，这样一来把数组大小设置为1235789就可以了。这样做也存在一定的问题: a != b 但 h(a) = h(b) = val 的情况是肯定存在的。问题也好解决，假设有m个数的h( )值都等于val，不妨把这m个值都用邻接表存起来（大致相当于A数组变成二维数组，只是第二维长度不定，m个数都存在A[ val ][ ]里 )，当要找q在不在A里时，就在A[ h(q) ][ ]里找，这个查找量比在所有数字中找要小的太多太多了，因为第二维会很短，毕竟h(a)=h(b)的情况并不多。
看懂了上述问题及分析也就知道了这个题怎么做，a1*x1^3+a2*x2^3+a3*x^3得到的所有的100*100*100个值就相当于上面1，75，324那7个值，逐个算出的 -1*(a4*x4^3+a5*x5^3)的所有值就相当于要查找的q，把答案统计出来即可。
注意：负数取模存在问题，而a1*x1^3+a2*x2^3+a3*x^3 与 (a4*x4^3+a5*x5^3)要想成为一组解，肯定互为相反数，不妨用unsigned long long 或 unsigned int类型再取模。
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 typedef unsigned long long ULL; 8 const int mod = 1235789; 9 struct A {10 ULL val;11 int next;12 }a[2000000];13 int cnt, head[mod];14 int a1, a2, a3, a4, a5, a6, ANS;15 inline ULL calc(int x,int y) {16 return x*y*y*y;17 }18 inline void insert(int x, int y, int z) {19 ULL tmp1 = calc(a1, x) + calc(a2, y) + calc(a3, z);20 int tmp2 = int(tmp1 % (ULL)mod);21 a[++cnt].val = tmp1;22 a[cnt].next = head[tmp2];23 head[tmp2] = cnt;24 }25 inline int ser(int x, int y) {26 ULL tmp1 = -1 * (calc(a4, x) + calc(a5, y));27 int tmp2 = int(tmp1 % (ULL)mod);28 int ans = 0;29 for (int i = head[tmp2]; i != -1; i = a[i].next) {30 if (a[i].val == tmp1) ans++;31 }32 return ans;33 }34 int main() {35 while (cin >> a1 >> a2 >> a3 >> a4 >> a5) {36 cnt = 0;37 for (int i = 0; i < mod; i++) head[i] = -1;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) {42 insert(i, j, k);43 }44 }45 }46 }47 ANS = 0;48 for (int i = -50; i <= 50; i++) {49 for (int j = -50; j <= 50; j++) {50 if (i != 0 && j != 0) {51 ANS += ser(i, j);52 }53 }54 }55 cout << ANS << endl;56 }57 return 0;58 }