#include <mpir.h>
#include <stdint.h>
#include <stdlib.h>
#include <math.h>


struct KeyValue{
    uint64_t value;
    unsigned int key;
};

int compare(const void* a, const void* b){
    return ( ((KeyValue*)a)->value - ((KeyValue*)b)->value );
}

bool find_in_array(KeyValue* arr, size_t len, uint64_t x, unsigned int &key){
    size_t first = 0;
    size_t last = len;

    size_t mid;
    if(last == 0)
        return false;
    if(arr[0].value > x)
        return false;
    if (arr[len - 1].value < x)
        return false;
    while (first < last){
        mid = first + (last - first) / 2;
        if (x <= arr[mid].value){
            last = mid;
        }else{
            first = mid + 1;
        }
    }
    if(arr[last].value == x){
        key = arr[last].key;
        return true;
    }
    return false;
}


int main(){
        mpz_t a, b, m;
        mpz_init_set_str(a,"2",10);
        mpz_init_set_str(b,"2",10);
        mpz_init_set_str(m,"7",10);
        const unsigned long long  n = 4;

        KeyValue* mem = (KeyValue*)calloc(n+1, sizeof(KeyValue));


        KeyValue* memp = mem;
        mpz_t tmp; mpz_init_set(tmp,b);
        mpz_t tmp2; mpz_init(tmp2);


        for(unsigned int x1=0;x1<=n;++x1){
            mpz_export(&(memp->value),NULL,0,sizeof(uint64_t),0,0,tmp);
            memp->key = x1;
            mpz_mul(tmp, tmp, a);
            mpz_mod(tmp,tmp,m);
            memp++;
        }
        printf("Table is build!\n");
        qsort(mem,n+1,sizeof(KeyValue),compare);
        printf("Table is sorted!\n");
        mpz_set_ui(tmp, 1);
        mpz_powm_ui(tmp2,a,n,m);
        uint64_t export_value;
        unsigned int x1;
        mpz_t tmp3; mpz_init(tmp3);
        for(unsigned int x0=0;x0<=n;++x0){
            mpz_export(&export_value,NULL,0,sizeof(uint64_t),0,0,tmp);
            if(find_in_array(mem, n+1, export_value, x1)){
                //printf("Founded: %u    ", export_value);
                mpz_set_ui(tmp3, x0*n - x1);
                if(mpz_cmp(tmp3, m) == -1){
                    printf("Answer: %u\n", x0*n - x1);
                    break;
                }
            }
            mpz_mul(tmp, tmp, tmp2);
            mpz_mod(tmp,tmp,m);
        }
        free(mem);
        return 0;
}