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

int brCifara(long long n) {
    int count = 0;
    while (n > 0) {
        count++;
        n /= 10;
    }
    return count;
}

int kaprekarov(long long n) {
    long long kv = n * n;
    int d = brCifara(n);

    long long levi = kv;
    long long desni = 0;

    long long base = 1;
    
    if (levi + desni == n) return 1;
    
    while (brCifara(desni) < d) {
        desni += base * (levi % 10);
        base *= 10;
        levi /= 10;
        
        if (levi + desni == n) return 1;
    }

    return 0;
}

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

    long long *locKap = malloc(10000 * sizeof(long long));
    long long *globalKap = NULL;
    
    int locCount = 0;

    for (long long i = 1 + id; i < 100000000; i += np) {
        if (kaprekarov(i)) locKap[locCount++] = i;
    }

    if (id != 0) {
        MPI_Send(&locCount, 1, MPI_INT, 0, 10, MPI_COMM_WORLD);
        MPI_Send(locKap, locCount, MPI_LONG_LONG, 0, 11, MPI_COMM_WORLD);
    } else {
        globalKap = malloc(10000 * sizeof(long long));
        int globalCount = 0;

        for (int i = 0; i < locCount; i++) 
            globalKap[globalCount++] = locKap[i];

        for (int i = 1; i < np; i++) {
            int recvCount;
            
            MPI_Recv(&recvCount, 1, MPI_INT, i, 10, MPI_COMM_WORLD, MPI_STATUS_IGNORE);
            MPI_Recv(&globalKap[globalCount], recvCount, MPI_LONG_LONG, i, 11, MPI_COMM_WORLD, MPI_STATUS_IGNORE);

            globalCount += recvCount;
        }

        for (int i = 0; i < globalCount; i++) 
            printf ("%lld ", globalKap[i]);

        free(globalKap);
    }

    free(locKap);
    MPI_Finalize();
}