注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

东月之神

在单纯的观念里面,生命就容易变得比较深刻!

 
 
 

日志

 
 
关于我

别驻足,梦想要不停追逐,别认输,熬过黑暗才有日出,要记住,成功就在下一步,路很苦,汗水是最美的书!

网易考拉推荐

(hash)hdu 1496 Equations  

2010-03-22 17:24:04|  分类: ACM |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Equations

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 899    Accepted Submission(s): 356


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
 

Author
LL
 

Source
 

Recommend
LL
 
 
解题报告:
题目意思很好理解,就是求有多少种方程的解的形式,输出来就可以了。
如果用4重循环的话,可能会超时,没有试过。。直接用hash一一对应就可以了。
2重循环把s = a*x1*x1+b*x2*x2 看做一个数组的下标,如果s > 0 ,hash1[s]++;若s <= 0; 则 hash2[-s]++;
再2重循环把s = c*x3*x3+d*x4*x4 看做下标,开始查找。多的不说直接代码。。很容易懂的、。、
code:

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int hash1[1000002], hash2[1000002];
int main()
{
    int a, b, c, d, i, j;   
    while(scanf("%d%d%d%d", &a, &b, &c, &d) != EOF)
    {
        if((a > 0 && b > 0 && c > 0 && d > 0) || (a < 0 && b < 0 && c < 0 && d < 0))
        {
            printf("0\n");
            continue;
      }
        int ans = 0, s;
        for(i = 0; i <= 1000001; i++)
            hash1[i] = hash2[i] = 0;
        for(i = 1; i <= 100; i++)
        {
            for(j = 1; j <= 100; j++)
            {
                s = a * i * i + b * j * j;
                if(s > 0)
                    hash1[s]++;
                else
                    hash2[-s]++;
            }
        }
        for(i = 1; i <= 100; i++)
        {       
            for(j = 1; j <= 100; j++)
            {
                s = c * i * i + d * j * j;
                if(s >= 0)
                 ans += hash2[s];
                else
                 ans += hash1[-s];
            }
        }
        printf("%d\n", 16 * ans);
    }
return 0;
}
  评论这张
 
阅读(1184)| 评论(3)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017