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

typedef struct _Entry {
    long long int key;
    int *value;
    struct _Entry *next;
} Entry;

typedef struct _HashTable {
    int size;
    Entry **table;    
} HashTable;

HashTable *ht_hash_table(int size) {
    
    // size of hash table must be positive
    assert (size >= 1);
    
    HashTable *hash_table = NULL;
    int i;
    
    // Allocate the hash table
    if ((hash_table = (HashTable *) malloc(sizeof(HashTable))) == NULL) {
        fprintf(stderr, "Failed to allocate hash table\n");
        return NULL;
    }

    // Allocate table for entries
    if ((hash_table->table = (Entry **) malloc(size * sizeof(Entry *))) == NULL) {
        fprintf(stderr, "Failed to allocate table for entries\n");
        return NULL;
    }
    
    // Initialize hash table
    hash_table->size = size;
    for (i = 0; i < size; i++) {
        hash_table->table[i] = NULL;
    }
    
    return hash_table;    
}

// Create an entry (key, value)
Entry *ht_entry(long long int key, int *value ) {
    Entry *entry;

    if ((entry = (Entry *) malloc(sizeof(Entry))) == NULL) {
        fprintf(stderr, "Failed to allocate entry\n");
        return NULL;
    }
    
    entry->key = key;
    entry->value = value;
    entry->next = NULL;

    return entry;
}

// Insert an entry into a hash table
void ht_set(HashTable *hash_table, long long int key, int *value ) {
    int pos = (int) (key % hash_table->size);
    Entry *entry = NULL;
    Entry *next = NULL;
    Entry *last = NULL;
    
    next = hash_table->table[pos];
    while (next != NULL) {
        if (next->key == key) return;
        last = next;
        next = next->next;
    }
    
    entry = ht_entry(key, value);
    if (last == NULL) {
        hash_table->table[pos] = entry;
    } else {
        last->next = entry;
    }
}

// Receive an entry with specified key from a hash table
int *ht_get(HashTable *hash_table, long long int key) {
    int pos = (int) (key % hash_table->size);
    Entry *entry = NULL;
    
    entry = hash_table->table[pos];
    while (entry != NULL && key != entry->key) {
        entry = entry->next;
    }
    
    if (entry == NULL) return NULL;
    return entry->value;
}

// return x^n
long long int tpow(long long int x, int n) {
    long long int res = 1;
    while (n > 0) {
        if (n & 1) res *= x;
        x *= x;
        n >>= 1;
    }
    return res;
}

int *create_array(int x1, int x2, int x3) {
    int *res = (int *) malloc(3 * sizeof(int));
    res[0] = x1, res[1] = x2, res[2] = x3;
    return res;
}

int gcd(int x, int y) {
    int z = 0;
    while (y > 0) {
        z = x, x = y, y = z % y;
    }
    return x;
}

int main(int argc, char *argv[]) {
    
    // x1^n + x2^n + x3^n + .. + xm^n = y^n
    // GCD(x1, x2, .., xm) = 1
    // n = 5, m = 4
    int i, x1, x2, x3, x4, y, g;
    long long int key;
    int *value;
    const int size = 39916801, MAX = 300;
    const int n = 5, m = 4;
    
    HashTable *hash_table = ht_hash_table(size);
    
    for (x1 = 1; x1 <= MAX; ++x1) {
        for (x2 = x1; x2 <= MAX; ++x2) {
            for (x3 = x2; x3 <= MAX; ++x3) {
                key = tpow(x1, n) + tpow(x2, n) + tpow(x3, n);
                value = create_array(x1, x2, x3);
                ht_set(hash_table, key, value);
            }
        }
    }
    
    printf("initialized hash table\n");
    printf("run time : %.3f\n", clock() * 1.0 / CLOCKS_PER_SEC);
    
    for (x4 = 1; x4 <= MAX; ++x4) {
        for (y = x4 + 1; y <= 3 * MAX; ++y) {
            key = tpow(y, n) - tpow(x4, n);
            value = ht_get(hash_table, key);
            if (value != NULL && value[2] <= x4) {
                g = x4;
                for (i = 0; i < 3; ++i) g = gcd(g, value[i]);
                if (g > 1) continue;
                printf("%d^%d + %d^%d + %d^%d + %d^%d = %d^%d\n", value[0], n, value[1], n, value[2], n, x4, n, y, n);
            }
        }
    }
    
    printf("run time : %.3f\n", clock() * 1.0 / CLOCKS_PER_SEC);
    
    return 0;
}