/*Filip Despotovic 37-2020*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <mpi.h>

#define MCW MPI_COMM_WORLD
#define N 100000000

int brojCifara( int n )
{
    if ( !n )
        return 0;

    return 1 + brojCifara( n / 10 );
}

int jeKaprekarov( long long int n )
{
    long long int kvadrat = n * n;
    int d = brojCifara( n );    
    int stepen, leviBroj, desniBroj;
    for(int i = 0; i < d; i++)
    {
        stepen = pow( 10, (i + 1) );
        leviBroj = kvadrat / stepen;
        desniBroj = kvadrat - leviBroj * stepen;
        if ( leviBroj + desniBroj == n )    
            return 1;
        
    }
    return 0;
}

int main()
{
    MPI_Init( NULL, NULL );
    int rank, size;
    MPI_Comm_rank( MCW, &rank );
    MPI_Comm_size( MCW, &size );

    int *a = (int*)calloc( (N + 1), sizeof(int) );
    
    for(long long int i = rank + 1; i <= N; i += size)
        if( jeKaprekarov( i ) )
            a[i] = 1;
    
    if( !rank )
        MPI_Reduce( MPI_IN_PLACE, a, N + 1, MPI_INT, MPI_LOR, 0, MCW );
    else
        MPI_Reduce( a, NULL, N + 1, MPI_INT, MPI_LOR, 0, MCW );
    
    /*
    if( !rank )
        for(int i = 1 ; i <= N; i++)
            if( a[i] )
                printf("%d\n", i);
    */
    MPI_Finalize();
    return 0;
}