当前位置: 代码迷 >> 综合 >> POJ1840 Eqs(hash)
  详细解决方案

POJ1840 Eqs(hash)

热度:62   发布时间:2024-01-16 13:35:51.0

题意:

已知a1,a2,a3,a4,a5,求a1x13+ a2x23+ a3x33+ a4x43+ a5x53=0有几个解。

要点:

跟hash其实关系不大,主要是移项,求a1x13+ a2x23+ a3x33=a4x43+ a5x33,这样只要三次循环即可,注意数组负数下标要加一个标准值。


15873510 Seasonal 1840 Accepted 49216K 719MS C++ 811B 2016-08-02 17:02:00
#include<iostream>
using namespace std;
const int maxn = 25000000;short Hash[maxn + 1];int main()
{int x1, x2, x3, x4, x5;int a1, a2, a3, a4, a5;int sum;cin >> a1 >> a2 >> a3 >> a4 >> a5;memset(Hash, 0, sizeof(Hash));for (x1 = -50; x1 <= 50; x1++){if (!x1)continue;for (x2 = -50; x2 <= 50; x2++){if (!x2)continue;sum =x1*x1*x1*a1 + x2*x2*x2*a2;if (sum < 0)sum += maxn;Hash[sum]++;}}int count = 0;for (x3 = -50; x3 <= 50; x3++){if (!x3)continue;for (x4 = -50; x4 <= 50; x4++){if (!x4)continue;for (x5 = -50; x5 <= 50; x5++){if (!x5)continue;sum = -(x3*x3*x3*a3 + x4*x4*x4*a4 + x5*x5*x5*a5);if (sum < 0)sum += maxn;count += Hash[sum];}}}cout << count << endl;return 0;
}