首页 > 代码库 > HDU1496Equations【hash】

HDU1496Equations【hash】

2024-07-24 05:48:12   225人阅读

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 -41 1 1 1
 

Sample Output

390880
 
分析：与上题相同
 
代码：
 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5  6 const int mod = 40007; 7  8 struct Node { 9     int to;10     int next;11 }e[mod + 10];12 13 int head[mod + 10];14 15 int tot;16 17 void Add(int u, int v) {18     e[tot].to = v;19     e[tot].next = head[u];20     head[u] = tot++;21 }22 23 int Find(int u, int v) {24     int cnt = 0;25     for(int i = head[u]; i; i = e[i].next) {26         if(e[i].to == v) cnt++;27     }28     return cnt;29 }30 31 void init() {32     memset(head, 0, sizeof(head));33     tot = 1;34 }35 36 int Fabs(int x) {37     return x > 0 ? x : - x;38 }39 40 int pre[105];41 42 int main() {43     int a, b, c, d;44     for(int i = 1; i <= 100; i++) {45         pre[i] = i * i;46     }47     while(EOF != scanf("%d %d %d %d",&a, &b, &c, &d) ) {48         init();49         for(int i = 1; i <= 100; i++) {50             for(int j = 1; j <= 100;    j++) {51                 int num = a * pre[i] + b * pre[j];52                 int p = Fabs(num) % mod;53                 Add(p, num);54             }55         } 56         int ans = 0;57         for(int i = 1; i <= 100; i++) {58             for(int j = 1; j <= 100;    j++) {59                 int num = c * pre[i] + d * pre[j];60                 int p = Fabs(num) % mod;61                 ans += Find(p, - num);62             }63         } 64         printf("%d\n", ans << 4);65     }66     return 0;67 }
View Code

 

HDU1496Equations【hash】


联系
我们