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

long const LIMIT = 10e8;

long power(long base, long exp)
{
    long i, res = 1;
    for(i = 0; i < exp; i++)
    {
        res *= base;
    }

    return res;
}

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

    return count;
}

int isKapernak(long n)
{
    int digitCount = getDigitCount(n);
    long square = n * n;
    long left = square / 10;
    long right = square % 10;
    
    int i = 0;
    while(i < digitCount)
    {
        if(left + right == n)
            return 1;
        
        right = (left % 10) * power(10, ++i) + right;
        left = left / 10;
    }

    return 0;
}

int main(int argc, char *argv[])
{
    long i;

    int id, np;

    MPI_Init(&argc, &argv);
    MPI_Comm_rank(MPI_COMM_WORLD, &id);
    MPI_Comm_size(MPI_COMM_WORLD, &np);

    double startTime;
    if(id == 0)
        startTime = MPI_Wtime();

    for(i = 1 + id; i < LIMIT; i += np)
    {
        if(isKapernak(i))
            printf("%ld\n", i);
    }


    if(id == 0)
    {
        double endTime = MPI_Wtime();
        printf("VREME %lf\n", endTime - startTime);
    }

    MPI_Finalize();
    return 0;
}