杭電acm1496

思路：首先，暴力會TLE，是以要把4個數分成2個和2個（關于這一點請閱讀《挑戰程式設計競賽》）。注意到a*x1^2+b*x2^2的範圍大小為2000000，我們不妨周遊前兩個數，計算并記錄在一個數組hash[]後，再周遊後兩個數，并在hash[]中直接查找，這樣複雜度就為O(n^2)(n=100)

完整代碼：

[cpp] view

plaincopy

1. /*187ms,8044KB*/  
2. #include<cstdio>  
3. #include<cstring>  
4. const int maxn = 1000000;  
5. int hash[2 * maxn + 5];  
6. int main()  
7. {  
8.     int a, b, c, d, i, j;  
9.     long long ans;  
10.     while (~scanf("%d%d%d%d", &a, &b, &c, &d))  
11.     {  
12.         if (a > 0 && b > 0 && c > 0 && d > 0 || a < 0 && b < 0 && c < 0 && d < 0)  
13.         {  
14.             puts("0");  
15.             continue;  
16.         }  
17.         memset(hash, 0, sizeof(hash));  
18.         for (i = 1; i <= 100; ++i)  
19.             for (j = 1; j <= 100; ++j)  
20.                 ++hash[a * i * i + b * j * j + maxn];  
21.         ans = 0L;  
22.         for (i = 1; i <= 100; ++i)  
23.             for (j = 1; j <= 100; ++j)  
24.                 ans += hash[-c * i * i - d * j * j + maxn];  
25.         printf("%I64d\n", ans << 4);  
26.     }  
27. }