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

#define MCI MPI_COMM_WORLD
#define N 1000000

int brojCifara(int n)
{
    if(n / 10 == 0)
        return 1;

    int brojac = 0;
    while(n)
    {
        n = n / 10 ;
        brojac++;
    }

    return brojac;

}

int Kapekarov(int n)
{
    int kv = n* n;
    int brCifara = brojCifara(n);

    for(int i = 0; i< brCifara; i++)
    {   
        int stepen = pow(10,(i+1));
        int levi = kv / stepen;
        int desni  = kv - levi * stepen;
        if(levi + desni == n){
            return 1;
        }
    }
    return 0;
}

int main()
{   
    int size,rank;
    double starttime, endtime;
    MPI_Init(NULL,NULL);
    //starttime = MPI_Wtime();
    MPI_Comm_rank(MCI,&rank);
    MPI_Comm_size(MCI,&size);

    
	     
	int *a =(int*)calloc((N+1),sizeof(int));

    for(int i = rank + 1; i <= N; i+=size)
           if (Kapekarov(i))
            a[i] = 1;   
    
    if(!rank)
        MPI_Reduce(MPI_IN_PLACE, a, N + 1 ,MPI_INT,MPI_LOR,0,MCI);
    else
        MPI_Reduce(a, NULL, N + 1 ,MPI_INT,MPI_LOR,0,MCI);
    

    if(! rank)
    {
        for(int i = 1 ; i < N ; i++)
        {
            if(a[i])
            printf("%d\n",i);
    
        }
    }
    //endtime  = MPI_Wtime();
	//printf("That took %f seconds\n",endtime-starttime);
    MPI_Finalize();
   
   
  
    return 0;
}