POJ1840 | 哈喽哈咯

Written by razrlele 23:02 December 20, 2014

Eqs

Time Limit: 5000MS		Memory Limit: 65536K
Total Submissions: 14507		Accepted: 7122

Description

Consider equations having the following form:
a1x1³+ a2x2³+ a3x3³+ a4x4³+ a5x5³=0
The coefficients are given integers from the interval [-50,50].
It is consider a solution a system (x1, x2, x3, x4, x5) that verifies the equation, xi∈[-50,50], xi != 0, any i∈{1,2,3,4,5}.

Determine how many solutions satisfy the given equation.

Input

The only line of input contains the 5 coefficients a1, a2, a3, a4, a5, separated by blanks.

Output

The output will contain on the first line the number of the solutions for the given equation.

Sample Input

1	37 29 41 43 47

Sample Output

654

Source

Romania OI 2002

首先要肯定是不能直接暴力的, 把五组数字分成两拨，一拨三个，一拨两个，前一拨o(100^3)打表，离散化后，对第二拨处理，从表中二分查找值，总共O(100^3+100^2*log(100^3)), 这样的话可以AC, 但是还也可以用Hash表优化, 优化过后速度可以提高一个数量级.

代码最优化原则: 只留下最高效的代码.

* File Name: poj1840.cpp

* Author: razrLeLe

* Mail: razrlele@outlook.com

* Homepage: https://yueyu.io

* Created Time: 2014年12月20日星期六 20时53分14秒

#include "vector"

#include "set"

#include "deque"

#include "queue"

#include "algorithm"

#include "functional"

#include "iostream"

#include "cstdio"

#include "cmath"

#include "cstdlib"

#include "string"

#include "cstring"

#include "string.h"

#include "map"

#include "cctype"

#include "list"

#include "stack"

using namespace std;

#define INF 0x3f3f3f3f

#define LOCAL

int cube[100];

char hash[25000010];

int main()

{

#ifdef LOCAL

freopen("/home/razrlele/build/data.txt", "r", stdin);

freopen("/home/razrlele/build/out.txt", "w", stdout);

#endif

int a[6], tmp;

for(int i = 1; i <= 5; i++)

scanf("%d", &a[i]);

int k = 0, ans = 0;

for(int i = -50; i <= 50; i++)

{

if(i == 0) continue;

cube[k++] = i*i*i;

}

for(int i = 0; i < 100; i++)

for(int j = 0; j < 100; j++)

{

tmp = -(cube[i]*a[1]+cube[j]*a[2]);

hash[tmp+12500000]++;

}

for(int i = 0; i < 100; i++)

for(int j = 0; j < 100; j++)

for(int k = 0; k < 100; k++) { tmp = cube[i]*a[3]+cube[j]*a[4]+cube[k]*a[5]; if(tmp > 12500000 || tmp < -12500000) continue;

else

ans += hash[tmp+12500000];

}

printf("%d\n", ans);

return 0;

}