hd1496----這道題是水水的數論嗎？ - acm1314－IT工程師數位筆記本

文章出處

題目：http://acm.hdu.edu.cn/showproblem.php?pid=1496

題意：

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.

這道題很水嗎？然而小恪并不這么認為，可能是小恪太水啦！。雖然此題思路很簡單，但是卻有兩個技巧值得學習！（也許機智的你，早已熟知這兩個技巧）。

第一步：變換公式 --> a*x1^2+b*x2^2=-c*x3^2-d*x4^2 （好像變換的很白癡，好像并沒有什么卵用！）

第二步：我們定義一個常數 shift 則： -->a*x1^2+b*x2^2+shift=-c*x3^2-d*x4^2+shift。（好像更沒什么卵用！，，，，，，）

第三步：直接看代碼，你就會明白。會明白這題雖然簡單但是真的很機智！

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

const int MAXN = 2e6+10;
const int shift = 1e6;
int f[MAXN];

int main()
{
    int a, b, c, d;
    while(cin>>a>>b>>c>>d)
    {
        int i, j, k, ans = 0;
        if(a<0&&b<0&&c<0&&d<0||a>0&&b>0&&c>0&&d>0)
        {
            cout<<0<<endl; continue;
        }
        memset(f, 0, sizeof(f));
        for(i=1; i<=100; i++)
        for(j=1; j<=100; j++)
        f[a*i*i+b*j*j+shift]++;
        for(i=1; i<=100; i++)
        for(j=1; j<=100; j++)
        ans+=f[-c*i*i-d*j*j+shift];
        cout<<ans*16<<endl;
    }
    return 0;
}

/* 
    數論， 
    變換公式-->a*x1^2+b*x2^2=-c*x3^2-d*x4^2-->a*x1^2+b*x2^2+shift=-c*x3^2-d*x4^2+shift。 
    分別枚舉x1,x2用哈希表記錄左式的所有值，再相同方法哈希右式，將相同的值得哈希值加入答案即可。 
    由于值可能為負，會數組溢出，所以加個偏移值shift 
*/