Equations HDU - 1496(哈希的应用)
2024-09-02 13:54:43
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
1 2 3 -4
1 1 1 1
Sample Output
39088
0
题目大意:
给你a,b,c,d这4个数的值,然后问a*x1^2 + b*x2^2 + c*x3^2 + d*x4^2 = 0
的(x1,x2,x3,x4)解一共有多少种?
思路:
要想直接暴力4层for循环是不可能的,但可以直接3层暴力;因为正负号不同不影响平方的效果,所以只枚举正数,最后乘以2的4次方(16),表示正负不同的组合:
操作代码如下:
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
int main()
{
int a,b,c,d;
while(~scanf("%d%d%d%d",&a,&b,&c,&d))
{
if(a>&&b>&&c>&&d>||a<&&b<&&c<&&d<)
{
printf("0\n");
continue;
}
int sum=;
for(int i=; i<=; i++)
for(int j=; j<=; j++)
for(int l=; l<=; l++)
{
int f=a*i*i+b*j*j+c*l*l;
if(f%d==)
{
int h=sqrt(abs((-f)/d));
if(h<=&&h>&&h*h==abs((-f)/d)&&f+d*h*h==)
sum++;
}
}
printf("%d\n",sum*);
}
return ;
}
另外一种可用哈希进行求解,分别把前两个数所算的总和:正数和负数放入两个不同的数组中,之后与后两个的负数与正数进行匹配看最终有多少种?结果还要 *16 哦!
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define maxx 1001001
int negative[maxx];//记录负数
int positive[maxx];//记录正数
int main()
{
int a,b,c,d;
while(~scanf("%d%d%d%d",&a,&b,&c,&d))
{
if(a>&&b>&&c>&&d>||a<&&b<&&c<&&d<)
{//abcd全部大于0或者小于0,肯定无解。要加上这个,不然超时
printf("0\n");
continue;
}
memset(negative,,sizeof(negative));
memset(positive,,sizeof(positive));
for(int i=; i<=; i++)
for(int j=; j<=; j++)
{
int k=a*i*i+b*j*j;
if(k<=)
negative[-k]++;//k<=0 负值[k]++
else
positive[k]++;//k>0 正值++
}
int sum=;
for(int i=; i<=; i++)
for(int j=; j<=; j++)
{
int k=c*i*i+d*j*j;
if(k<)
sum+=positive[-k];//若k为负,加上正值
else
sum+=negative[k]; //若k为正,加上负值
}
printf("%d\n",*sum); //每个解有正有负,结果有2^4种
}
return ;
}
最新文章
- SQL Server 合并复制遇到identity range check报错的解决
- BSBuDeJie_03
- web cache server方案比较:varnish、squid、nginx
- Font Awesome符号字体
- oracle-表空间满了
- WebDriver 随笔
- C#反射(转载)
- tomcat 解析(一)-文件解析
- js jsp 时间 日期 控件 插件 简单 实用
- Django Web开发【6】使用Ajax增强用户体验
- SuperSocket源码解析之配置系统
- “此主机支持 Intel VT-x,但 Intel VT-x 处于禁用状态”的问题的解决
- docker 3 docker安装
- QTP自动化测试-笔记 注释、大小写
- CMakeLists
- 动态HTMl处理
- Secure backup
- Window环境下RabbitMQ的安装和配置教程
- 口琴练习部分 - 多孔单音奏法 &; 简单伴奏
- [置顶] Hadoop2.2.0中HDFS的高可用性实现原理
热门文章
- Luogu [P3622] [APIO2007]动物园
- form 表单提交数据和文件(fromdata的使用方法)
- 图论——最短路:Floyd,Dijkstra,Bellman-Ford,SPFA算法及最小环问题
- jdbc相比于hibernate的弊端
- 关于安卓端 点击button时出现橙色边框
- react hook的todolist
- kotlin中接口
- ubuntu Tensorflow object detection API 开发环境搭建
- SQLAlchemy如何筛选值为None的列?那么django呢
- Python3 Selenium自动化web测试 ==>;FAQ:日期格式和日期字符串格式相互转换