Equations
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1729 Accepted Submission(s): 662
Problem Description
Consider equations having the following form:
a*x1^2+b*x2^2+c*x3^2+d*x4^2=0
a, b, c, d are integers from the interval [-50,50] and any of them cannot be 0.
It is consider a solution a system ( x1,x2,x3,x4 ) that verifies the equation, xi is an integer from [-100,100] and xi != 0, any i ∈{1,2,3,4}.
Determine how many solutions satisfy the given equation.
Input
The input consists of several test cases. Each test case consists of a single line containing the 4 coefficients a, b, c, d, separated by one or more blanks.
End of file.
Output
For each test case, output a single line containing the number of the solutions.
Sample Input
Sample Output
题目大意,给你a,b,c,d这4个数的值,然后问a*x1^2 + b*x2^2 + c*x3^2 + d*x4^2 = 0
的(x1,x2,x3,x4)解一共有多少种?
初看这题,想直接4次循环找,但是这样绝对超时,所以就用了hash这种方法来解决,很巧妙!分开两部分求和,若两部分的和是0,则就加上那么多种,最后乘以16。这样就能从n^4变成2*n^2,速度快了很多很多!!!
代码:
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <memory.h>
using namespace std;
int f1[1000005]; //保存得数是正的
int f2[1000005]; //保存得数是负的
int main()
{
int i, j, k, sum;
int a, b, c, d;
while(scanf("%d %d %d %d", &a, &b, &c, &d) != EOF)
{
//abcd全部大于0或者小于0,肯定无解。要加上这个,不然超时
if(a>0 && b>0 && c>0 && d>0 || a<0 && b<0 && c<0 && d<0)
{
printf("0\n");
continue;
}
memset(f1, 0, sizeof(f1));
memset(f2, 0, sizeof(f2));
for(i = 1; i <= 100; i++)
{
for(j = 1; j<= 100; j++)
{
k = a*i*i + b*j*j;
if(k >= 0) f1[k]++; //k>=0 f1[k]++
else f2[-k]++; //k<0 f2[k]++
}
}
sum = 0;
for(i = 1; i <= 100; i++)
{
for(j = 1; j<= 100; j++)
{
k = c*i*i + d*j*j;
if(k > 0) sum += f2[k]; //若k为正,加上的f2[k]
else sum += f1[-k]; //若k为负,加上的f1[k]
}
}
printf("%d\n", 16*sum); //每个解有正有负,结果有2^4种
}
return 0;
}
分享到:
相关推荐
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
HDUACM2010版_14)Hash及应用HDUACM2010版_14)Hash及应用HDUACM2010版_14)Hash及应用HDUACM2010版_14)Hash及应用
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 1166线段树代码
HDU最全ac代码
hdu动态规划算法集锦
自己做的HDU ACM已经AC的题目
hdu题目分类
HDU图论题目分类