Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 104 Solved: 22
[Submit][Status][Web Board]
Description
Input
Output
Sample Input
Sample Output
题解：
a*x+a*x+a*x+a*x+a*x= 0
<==> a*x+a*x+a*x= -1*(a*x+a*x)
可以想办法利用三重循环枚举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类型再取模。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
typedef unsigned long long ULL;
const int mod = ;
struct A {
ULL val;
int next;
}a[];
int cnt, head[mod];
int a1, a2, a3, a4, a5, a6, ANS;
inline ULL calc(int x,int y) {
return x*y*y*y;
}
inline void insert(int x, int y, int z) {
ULL tmp1 = calc(a1, x) + calc(a2, y) + calc(a3, z);
int tmp2 = int(tmp1 % (ULL)mod);
a[++cnt].val = tmp1;
a[cnt].next = head[tmp2];
head[tmp2] = cnt;
}
inline int ser(int x, int y) {
ULL tmp1 = - * (calc(a4, x) + calc(a5, y));
int tmp2 = int(tmp1 % (ULL)mod);
int ans = ;
for (int i = head[tmp2]; i != -; i = a[i].next) {
if (a[i].val == tmp1) ans++;
}
return ans;
}
int main() {
while (cin >> a1 >> a2 >> a3 >> a4 >> a5) {
cnt = ;
for (int i = ; i < mod; i++) head[i] = -;
for (int i = -; i <= ; i++) {
for (int j = -; j <= ; j++) {
for (int k = -; k <= ; k++) {
if (i != && j != && k != ) {
insert(i, j, k);
}
}
}
}
ANS = ;
for (int i = -; i <= ; i++) {
for (int j = -; j <= ; j++) {
if (i != && j != ) {
ANS += ser(i, j);
}
}
}
cout << ANS << endl;
}
return ;
}