//Pablo Soares Dias    31821BSI007
//Bruno Ferreira Silva  31521BSI005
#include <stdio.h>
#include <math.h>

unsigned long long int  contar(long long int num){

    if(num<10) return 1;

    return contar(num/10)+1;

    }

unsigned long long int  high(long long int  num){

    unsigned long long int  x=contar(num)/2;

    x=num/pow(10,x);

    return x;

    }

unsigned long long int low(long long int  num){

    long long int x=contar(num)/2;

    x=num%((long long int)(pow(10,x)));

    return x;
    }

unsigned long long int karatsuba(double  num1,double  num2){

  if (num1 < 10||num2 < 10)
       return num1*num2;


  int m=fmax(contar(num1),contar(num2));

  int m2 =ceil (m/2);

  unsigned  long long int a = high(num1);
  unsigned  long long int b = low(num1);
  unsigned  long long int c = high(num2);
  unsigned  long long int d = low(num2);


  unsigned long long int  z0 = karatsuba(b,d);
  unsigned long long int  z2 = karatsuba(a,c);
  unsigned long long int  z1=karatsuba(a+b,c+d)-z2-z0;


  return (z2*pow(10,m2*2))+(z1*pow(10,m2))+(z0);

  }


int main(){

    long long int x,y;

    printf("Digite um valor 1: ");
    scanf("%lli",&x);

    printf("Digite um valor 2: ");
    scanf("%lli",&y);

    printf("%lli\n",x*y);
    printf("%lli\n",karatsuba(x,y));


   return 0;
}