#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){
    //uint64_t f = ((KeyValue*)a)->value;
    //uint64_t s = ((KeyValue*)b)->value;
    //if(f == s)
    //  return 0;
    //if(f < s)
    //  return -1;
    //return 1;
    return ( ((KeyValue*)a)->value - ((KeyValue*)b)->value );
}
bool find_in_arr(KeyValue* arr, size_t len, uint64_t x, unsigned int &key){
    for(size_t a = 0; a<len; ++a){
        if((arr+a)->value == x){
            key = a;
            return true;
        }
    }
    return false;

}
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,"3",10);
        mpz_init_set_str(b,"13",10);
        mpz_init_set_str(m,"17",10);
        const unsigned long long  n = 16;*/


        mpz_init_set_str(a,"6511709995802996252529428210009069141516455100602512742258547866292839663070281213795462953359084389612327175129512390242393774885156190907043183764572298",10);
        mpz_init_set_str(b,"4016751268155181878780762958485595786864539552267966173503519872828650364102948010668074636189225260885467109630266705699778224615794326630829490560742794",10);
        mpz_init_set_str(m,"9913033868557133667485171584043308894354447793802229576147965224579616862439637051468618269920939124273132778910108308880842351094700094598897767100778663",10);
        const unsigned long long  n = 1048576;



        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);

        uint64_t* export_buffer = new uint64_t[8];


        for(unsigned int x1=0;x1<=n;++x1){
            mpz_export(export_buffer,NULL,0,sizeof(uint64_t),0,0,tmp);
            memp->key = x1;
            memp->value = export_buffer[0];
            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");
        FILE* f = fopen("test13.txt","w");
        for(unsigned int i=0;i<n;++i){
            fprintf(f,"%u\n",mem[i].value);
        }
        fclose(f);
        FILE* f2 = fopen("test2.txt","w");
        mpz_set_ui(tmp, 1);
        mpz_powm_ui(tmp2,a,n,m);
        unsigned int x1;
        mpz_t tmp3; mpz_init(tmp3);
        for(unsigned int x0=0;x0<=n;++x0){
            mpz_export(export_buffer,NULL,0,sizeof(uint64_t),0,0,tmp);
            fprintf(f2,"%u\n",export_buffer[0]);
            if(find_in_array(mem, n+1, export_buffer[0], x1)){
                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);
        }
        fclose(f2);
        free(mem);
        delete[] export_buffer;
        return 0;
}