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

#define LIMIT 100000000

int kaprekanov_broj(int x)
{
    int daLiJeKaprekanov=0;
    int kvadratBroja=x*x;
    int brCifara=0;
    int leviDeo=0;
    int desniDeo=0;
    int cuvamoX=kvadratBroja;

    while(x>0)
    {
        brCifara++;
        kvadratBroja/=10;
    }
    kvadratBroja=cuvamoX;
    
    int brCifaraDesno=0;
    int brCifaraLevo=brCifara;

    leviDeo=kvadratBroja;
    desniDeo=0;

    if(leviDeo+desniDeo==x) 
    {
        daLiJeKaprekanov=1;
    }

    while(brCifaraLevo!=brCifaraDesno)
    {
        int pomKvadratBroja=kvadratBroja;
        for(int i=0;i<brCifaraDesno;i++)
        {
            int stepen=1;
            desniDeo+=stepen*(pomKvadratBroja%10);
            stepen*=10;
        }

        leviDeo=pomKvadratBroja;

        if(leviDeo+desniDeo==x)
        {
            daLiJeKaprekanov=1;
        }
        
        brCifaraLevo++;
        brCifaraDesno--;
    }
    return daLiJeKaprekanov;
}

int main(int argc,char **argv)
{
    int id,np;
    MPI_Init(argc,argv);

    MPI_Comm_rank(MPI_COMM_WORLD,&id);
    MPI_Comm_size(MPI_COMM_WORLD,&np);

    int n=LIMIT;
    MPI_Bcast(&n,1,MPI_INT,0,MPI_COMM_WORLD);

    int base=n/np;
    int rem=n%np;

    int *sendcounts=NULL;
    int *displs=NULL;

    if(id==0)
    {
        *sendcounts=(int*)malloc(np*sizeof(int));
        *displs=(int*)malloc(np*sizeof(int));
        int offset=0;
        for(int p=id+1;p<n;p+=np)
        {
            int cnt=base+(p<rem?1:0);
            sendcounts[p]=cnt;
            displs[p]=offset;
            offset+=cnt;
        }
    }

    int localN=base+rem;
    int *localNiz=(int*)malloc(localN*sizeof(int));
    int *globalNiz;
    MPI_Scatterv(globalNiz,sendcounts,displs,MPI_INT,localNiz,localN,MPI_INT,0,MPI_COMM_WORLD);

    for(int i=0;i<localN;i++)
    {
        localNiz[i]=(kaprekanov_broj(localNiz[i]));
    }

    
    MPI_Gatherv(localNiz,sendcounts,MPI_INT,globalNiz,localN,displs,MPI_INT,0,MPI_COMM_WORLD);

    int *noviNiz=(int*)malloc(n*sizeof(int));
    if(id==0)
    {
        int indeks=0;
        for(int i=0;i<n;i++)
        {
            if(globalNiz[i]==1)
            {
                noviNiz[indeks++]=i;
            }
        }

        for(int j=0;j<indeks;j++)
        {
            printf("%d",noviNiz[j]);
        }
    }

    MPI_Finalize();
    return 0;
}