Hdu 1496 Equations(巧妙哈希)

阳光穿透心脏的1/2处 2022-05-17 12:55 147阅读 0赞

[题目链接][Link 1]

题目大意：给你一个方程：a\*x1^2+b\*x2^2+c\*x3^2+d\*x4^2=0，输入方程的4个系数，求出它的解的个数，其中系数 ai∈\[-50,50\] xi∈\[-100,0）∪（0,100\]。

分析：将方程移项可以得到：a\*x1^2 + b\*x2^2 = -c\*x3^2 - d\*x4^2 的形式，两层循环1-100枚举左边两个根的所有值，将方程左边的值存入映射数组Hash中，注意这里应该是Hash数组值++，而不是Hash数组值=1，例如，如果a=b的时候，那么x1和x2的值是可以互换的，如果是让Hash数组的值=1的话就会漏掉一部分解。

然后再枚举方程右边的解，只需要两层枚举1-100即可，用答案值加上每种解的情况的Hash数组的值，再让答案乘16，（因为每个解都可以为正或者为负，4个解就是2^4）。这样总复杂度就可以由枚举四个解时的O（n^4）降低到O（2\*n^2）。

#include<bits/stdc++.h>
    #define Clear(x) memset(x,0,sizeof(x))
    typedef long long ll;
    typedef unsigned long long ull;
    using namespace std;
    const int maxn=2e6+7;
    const int prime=1e6+1;
    int Hash[maxn];
    
    int main()
    {
        int a,b,c,d;
        while(scanf("%d%d%d%d",&a,&b,&c,&d)!=EOF)
        {
            if(a*b>0&&b*c>0&&c*d>0){
                printf("0\n");
                continue;
            }
            Clear(Hash);
            for(int i=1;i<=100;i++)
            {
                for(int j=1;j<=100;j++)
                {
                    Hash[a*i*i+b*j*j+prime]++;
                }
            }
            int ans=0;
            for(int i=1;i<=100;i++)
            {
                for(int j=1;j<=100;j++)
                {
                    ans+=Hash[-c*i*i-d*j*j+prime];
                }
            }
            printf("%d\n",16*ans);
        }
        return 0;
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=1496