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

int num_len(long number){
    int length = 0;
    while(number > 0){
        // printf("Checking %ld\n", number);
        number /= 10;
        length++;
    } 
    return length;
}

long return_number(long arr[], int length){
    long sum = arr[0];
    long factor_10 = 10;
    int i = 1;
    while(i < length){
        sum += arr[i] * factor_10;
        factor_10 *= 10;
        i++;
    }

    return sum;
}

int check_kaperkar(int number){
    long square = number * number;
    int square_len = num_len(square);

    long left_arr[10], right_arr[10];
    long left, right;

    int i = 0;
    if(square_len % 2 == 0){
        while(i < square_len/2){
            right_arr[i++] = square % 10;
            square /= 10;
        }

        i = 0;
        while(i < square_len/2){
            left_arr[i++] = square % 10;
            square /= 10;
        }
        right = return_number(right_arr, square_len/2);
        left = return_number(left_arr, square_len/2);
        // printf("right: %ld, left: %ld\n", right, left);
    }

    if(square_len % 2 != 0){
        // printf("square_len %d\n", square_len/2);
        i = 0;
        while(i < square_len/2 + 1){
            right_arr[i++] = square % 10;
            square /= 10;
        }

        i = 0;
        while(i < square_len/2){
            left_arr[i++] = square % 10;
            square /= 10;
        }
        right = return_number(right_arr, square_len/2 + 1);
        left = return_number(left_arr, square_len/2);
        // printf("right: %ld, left: %ld\n", right, left);
    }


    if(left + right == number) return 1;
    return 0;
}

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 = 100000000;
    // int n;
    // if(!id){
    //     printf("Unesi n: \n");
    //     scanf("%d", &n);
    // }
    double wstart = MPI_Wtime(), endtime;

    MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);

    for(int i = id; i <= n; i+=np){
        // printf("Process %d: checking for %d\n", id, i);
        if(check_kaperkar(i)){
            printf("Process %d: %d is Kaperkars number\n", id, i);
        }
    }

    if(!id){
        endtime = MPI_Wtime();
        printf("Exit time: %lf.", endtime);
    }

    MPI_Finalize();
    return 0;
}