Eqs

时间：2010-06-10 来源：buptstehc

题目来源：Eqs
首先枚举a1*x1*x1*x1 + a2*x2*x2*x2的所有取值，并将结果哈希保存在链表中，然后枚举-a3*x3*x3*x3 - a4*x4*x4*x4 - a5*x5*x5*x5并判断是否有相同的取值。

#include <stdio.h>
#include <stdlib.h>

#define MAX 100001
typedef struct node
{
    struct node *next;
    int data, count;
}node;
node list[MAX], *prev, *cur, *nd;

int main(void)
{
    int a1, a2, a3, a4, a5, i, j, k, hash, sum, cnt;

    scanf("%d%d%d%d%d", &a1, &a2, &a3, &a4, &a5);
    for(i = -50; i <= 50; i++)
        for(j = -50; j <= 50; j++)
        {
            if(0 == i || 0 == j)
                continue;

            sum = a1 * i * i * i + a2 * j * j * j;
            hash = sum % MAX;
            if(hash < 0)
                hash += MAX;
            if(!list[hash].count)
            {
                list[hash].count++;
                list[hash].data = sum;
            }
            else
            {
                cur = list + hash;
                while(cur && (sum != cur -> data))
                {
                    prev = cur;
                    cur = cur -> next;
                }

                if(!cur)
                {
                    nd = (node *)malloc(sizeof(node));
                    nd -> next = 0;
                    nd -> data = sum;
                    nd -> count = 1;
                    prev ->next = nd;
                }
                else
                    cur -> count++;
            }
        }

    cnt = 0;
    for(i = -50; i <= 50; i++)
        for(j = -50; j <= 50; j++)
            for(k = -50; k <= 50; k++)
            {
                if(0 == i || 0 == j || 0 == k)
                    continue;

                sum = -a3 * i * i * i - a4 * j * j * j - a5 * k * k * k;
                hash = sum % MAX;
                if(hash < 0)
                    hash += MAX;
                if(!list[hash].count)
                    continue;
                else
                {
                    cur = list + hash;
                    while(cur && (sum != cur -> data))
                    {
                        prev = cur;
                        cur = cur -> next;
                    }

                    if(cur)
                        cnt += cur -> count;
                }
            }

    printf("%d\n", cnt);

    return 0;
}