HDU 1496 (Hash)

2725 단어 STL

G - Equations
Time Limit: 3000 MS Memory Limit: 32768 KB
64-bit integer IO format: %I64d , %I64u Java class name: Main
[Submit] [Status]
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

 
제목:
a, b, c, d 를 지정 하여 a * x1 * x1 + b * x2 * x2 + c * x3 * x3 + d * x4 * x4 = 0 의 해 를 만족 시 키 는 개수 xi! =0。
 
생각:
n ^ 4 폭력 은 시간 을 초과 할 수 있 습 니 다. 방정식 을 두 부분 으로 나 눌 수 있 습 니 다. t = a * x1 * x1 + b * x2 * x2 * x2 모든 가능 한 답 을 한 번 옮 겨 다 닐 수 있 습 니 다. t > = 0 이면 zh [t] + 1, 그렇지 않 으 면 fu [t] + 1 을 다시 t = c * x3 * x3 + d * x4 * x4 의 값 을 한 번 옮 겨 다 닐 수 있 습 니 다. t > 0 이면 fu [t] 중의 해 수 를 보 세 요. 그렇지 않 으 면 zh [t] 를 보 세 요.마지막 으로 결 과 를 16 에 곱 합 니 다. 모든 x 는 하나의 양수 와 마이너스 가 있 기 때 문 입 니 다. 즉, 2 ^ 4 개 입 니 다.
코드:
#include 
#include 
#include 
#define LL long long
using namespace std;
int fu[1000005], zh[1000005];
int main()
{
    int a, b, c, d;
    while(~scanf("%d%d%d%d", &a, &b, &c, &d))
    {
        if((a>0&&b>0&&c>0&&d>0)||(a<0&&b<0&&c<0&&d<0))    /// a,b,c,d  ,     
            printf("0
"); else{ memset(fu, 0, sizeof(fu)); memset(zh, 0, sizeof(zh)); for(int i=1; i<=100; i++){ for(int j=1; j<=100; j++){ int temp = a*i*i + b*j*j; if(temp >= 0) zh[temp] ++;    /// else fu[-temp] ++;    /// } } int ans = 0; for(int i=1; i<=100; i++){ for(int j=1; j<=100; j++){ int temp = c*i*i + d*j*j; if(temp > 0) ans += fu[temp];    /// else ans += zh[-temp];    /// } } printf("%d
", ans*16);    /// 2^4=16 } } }

 
 

좋은 웹페이지 즐겨찾기