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

int brojCifara(int x)
{
    int temp = x;
    int br = 0;

    while(temp > 0)
    {
        temp = temp / 10;
        br++;
    }

    return br;
}

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

int jeKaprekarov(int n)
{
    int pom = n;
    int kvadrat = n * n;

    // int brCif = brojCifara(x);
    // int niz[brCif];

    // int i = 0;
    // while(temp > 0)
    // {
    //     trCifra = temp % 10;
    //     temp = temp / 10;

    //     niz[i] = trCifra;
    //     i++;
    
    // }

    int deli = 1;
    int l, d;

    while(pom > 0)
    {
        deli = deli * 10;
        pom = pom / 10;

        l = kvadrat / deli;
        //printf("Br cif levo %d\n", brojCifara(l));
        d = kvadrat % deli;
        //printf("Br cif desno %d\n", brojCifara(d));
    }

    if(l + d == n) 
        return 1;
    return 0;
}

int main(int argc, char** argv)
{

    MPI_Init(&argc, &argv);

    int rank, size;

    MPI_Comm_rank(MPI_COMM_WORLD, &rank);
    MPI_Comm_size(MPI_COMM_WORLD, &size);

    int n = pow(10, 8);
    int brKaprekarovih = 0;

    // int* globalniNiz = calloc(n, sizeof(int)); 
    // int* lokalniNiz = malloc(n * sizeof(int));

    // for(int i = rank + 1; i < n; i += size)
    // {
    //     if(jeKaprekarov(i))
    //     {
    //         lokalniNiz[i] = 1;
    //         brKaprekarovih++;
    //     }
    // }

    // MPI_Reduce(lokalniNiz, globalniNiz, n, MPI_INT, MPI_LOR, 0, MPI_COMM_WORLD);

    int *niz = malloc(n * sizeof(int));
    
    int rootSize;
    int count = 0;
    MPI_Status status;

    for(int i = rank + 1; i < n; i += size)
    {
        if(jeKaprekarov(i))
        {
            niz[count++] = i;
            printf("i:%d\n", i);
        }
    }

    if(rank != 0)
    {
        MPI_Send(niz, count, MPI_INT, 0, 42, MPI_COMM_WORLD);
    }
    else
    {
        rootSize = count;

        for(int i = 1; i < size; i++)
        {
            int velicina;
            MPI_Probe(i, 42, MPI_COMM_WORLD, &status);
            MPI_Get_count(&status, MPI_INT, &count);
            MPI_Recv(niz + rootSize, count, MPI_INT, i, 42, MPI_COMM_WORLD, &status);
            
            rootSize += count;
        }
    }

    // for(int i=0; i<n; i++)
    // {
    //     if(globalniNiz[i])
    //         printf("%d\n", i);
    // }

    for(int i=0; i<rootSize; i++)
    {
        printf("%d\n", i);
    }

    // double vreme = MPI_Wtime();
    // printf("Vreme izvrsavanja: %f", vreme);

    MPI_Finalize();

    return 0;
}