#include <stdio.h>
#include <string.h>
#include <ctype.h>

/* Program demonstrira algoritme za racunske operacije nad neoznacenim
   celim brojevima u proizvoljnoj osnovi */

#define MAX_STR 1000

/* Funkcija uzima karakter i prevodi ga u vrednost cifre. Za cifre se
   koriste karakteri '0' - '9' i 'A' - 'Z'  */
unsigned karakter_u_cifru(char c)
{
  return isdigit(c) ? c - '0' : c - 'A' + 10;
}

/* Funkcija uzima vrednost cifre i prevodi je u karakter kojim se ta 
   cifra oznacava */
char cifra_u_karakter(unsigned d)
{
  return d < 10 ? d + '0' : d - 10 + 'A';
}

/* Konvertuje zapis broja x iz osnove b u binarni zapis, koristeci algoritam
   zasnovan na sumi */
void konvertuj_u_binarni(char * x, unsigned b, unsigned * r)
{
  int i;
  unsigned xc;
  *r = 0;
  for(i = 0; x[i] != '\0'; i++)
    {
      xc = karakter_u_cifru(x[i]);
      *r = *r * b + xc;
    }
}

/* Pomocna funkcija obrce string */
void obrni_string(char * s)
{
  int n = strlen(s);
  int i, j;
  for(i = 0, j = n - 1; i < j; i++, j--)
    {
      unsigned t = s[i];
      s[i] = s[j];
      s[j] = t;
    }
}

/* Konvertuje binarni zapis broja x u zapis sa osnovom b, algoritmom
   zasnovanom na deljenju */
void konvertuj_iz_binarnog(unsigned x, unsigned b, char * r)
{
  unsigned i = 0;
  while(x != 0)
    {
      r[i++] = cifra_u_karakter(x % b);
      x = x / b;
    }
  r[i] = '\0';
  obrni_string(r);
}

/* Konvertuje zapis broja iz osnove b1 u b2 (koristeci binarni zapis
   kao posredni) */
void konvertuj_zapis(char * x, unsigned b1, unsigned b2, char * r)
{
  unsigned v;
  konvertuj_u_binarni(x, b1, &v);
  konvertuj_iz_binarnog(v, b2, r);
}

/* Funkcija sabira dva broja u osnovi b. Pretpostavlja se da su brojevi 
   iste duzine i da su predstavljeni stringovima x i y. Rezultat se smesta
   u string na koji pokazuje r, dok se informacija o prekoracenju upisuje u
   lokaciju na koju pokazuje c */
void sabiranje(char * x, char * y, unsigned b, char * r, unsigned * c)
{
  unsigned xc, yc, rc, pc = 0;
  int i;
  int n = strlen(x);
  for(i = n - 1; i >= 0 ; i--)
    {
      xc = karakter_u_cifru(x[i]);
      yc = karakter_u_cifru(y[i]);
      rc = (xc + yc + pc) % b;
      pc = (xc + yc + pc) / b;
      r[i] = cifra_u_karakter(rc);
    }
  r[n] = '\0';
  *c = pc;
}

/* Funkcija oduzima dva broja u osnovi b. Pretpostavlja se da su brojevi 
   iste duzine i da su predstavljeni stringovima x i y. Rezultat se smesta
   u string na koji pokazuje r, dok se informacija o prekoracenju upisuje u
   lokaciju na koju pokazuje c */
void oduzimanje(char * x, char * y, unsigned b, char * r, unsigned * c)
{
  unsigned xc, yc, rc, pc = 0;
  int i;
  int n = strlen(x);
  for(i = n - 1; i >= 0 ; i--)
    {
      xc = karakter_u_cifru(x[i]);
      yc = karakter_u_cifru(y[i]);
      unsigned p = xc < (yc + pc);
      rc = !p ? xc - (yc + pc) : xc + b - (yc + pc);
      pc = p;
      r[i] = cifra_u_karakter(rc);
    }
  r[n] = '\0';
  *c = pc;
}

/* Funkcija dodaje k nula iza zapisa broja (ekvivalentno mnozenju sa b^k) */
void dodaj_k_pratecih_nula(char * x, unsigned k)
{
  int n = strlen(x);
  while(k)
    {
      x[n++] = '0';
      k--;
    }
  x[n] = '\0';   
}

/* Funkcija dodaje k nula ispred zapisa broja (ne utice na vrednost broja) */
void dodaj_k_vodecih_nula(char * x, unsigned k)
{
  int n = strlen(x);
  x[n + k] = '\0';
  while(n)
    {
      n--;
      x[n + k] = x[n]; 
    }
  while(k)
    {
      k--;
      x[k] = '0';
    }
}

/* Funkcija brise vodece nule iz zapisa broja */
void obrisi_vodece_nule(char * x)
{
  int i = 0, j = 0;
  while(x[i] == '0') i++; /* Preskacemo sve vodece nule */

  while(x[i] != '\0') /* Prepisujemo ostale cifre na pocetak */
    x[j++] = x[i++];

  if(j != 0)
    x[j] = '\0';
  else /* Specijalni slucaj: kada su sve cifre nule, treba ostaviti jednu */
    {
      x[0] = '0';
      x[1] = '\0';
    }
}

/* Funkcija dodaje odgovarajuci broj vodecih nula ispred "kraceg" broja, kako
   bi imali isti broj cifara */
void izjednaci_sirine_zapisa(char * x, char * y)
{
  int nx = strlen(x), ny = strlen(y);
  if(nx < ny)
    dodaj_k_vodecih_nula(x, ny - nx);
  else if(nx > ny)
    dodaj_k_vodecih_nula(y, nx - ny);
}

/* Funkcija vrsi sabiranje, pri cemu u slucaju postojanja (n + 1)-ve cifre
   (koja je u tom slucaju 1) ne vraca signal za prekoracenje, vec prosiruje
   rezultat, dodajuci mu jos jednu vodecu jedinicu */
void prosireno_sabiranje(char * x, char * y, unsigned b, char * r)
{
  unsigned c;
  sabiranje(x, y, b, r, &c);
  if(c != 0) /* Ako imamo prekoracenje, dopisujemo jedinicu na pocetak */
    {
      dodaj_k_vodecih_nula(r, 1);
      r[0] = '1';
    }
}

/* Funkcija mnozi broj x u osnovi b cifrom c (0 <= c < b). Rezultat se
   smesta u string na koji pokazuje r */
void mnozenje_cifrom(char * x, unsigned b, unsigned c, char * r)
{
  int n = strlen(x);
  int i;
  unsigned xc, t, rc, pc = 0;
  for(i = n - 1; i >= 0; i--)
    {
      xc = karakter_u_cifru(x[i]);
      t = xc * c + pc;
      rc = t % b;
      pc = t / b;
      r[i] = cifra_u_karakter(rc);      
    }
  r[n] = '\0'; /* Mora se zatvoriti string */

  /* Ako je preostala jos jedna cifra, tada dodajemo vodecu nulu na rezultat,
     a zatim je "prepravljamo" u odgovarajucu cifru */
  if(pc != 0)
    {
      dodaj_k_vodecih_nula(r, 1);
      r[0] = cifra_u_karakter(pc);
    }
}

/* Funkcija mnozi dva neoznacena cela broja u osnovi b */
void mnozenje(char * x, char * y, unsigned b, char * r)
{
  int ny = strlen(y);
  int i;
  unsigned yc;
  r[0] = '\0';
  char s[MAX_STR]; /* Pomocni string u koji smestamo proizvod sa i-tom cifrom */
  for(i = ny - 1; i >= 0; i--)
    {
      yc = karakter_u_cifru(y[i]);
      mnozenje_cifrom(x, b, yc, s);
      dodaj_k_pratecih_nula(s, ny - 1 - i);
      izjednaci_sirine_zapisa(s, r);
      prosireno_sabiranje(s, r, b, r);
    }
  obrisi_vodece_nule(r); /* Vodece nule ovde mogu da nastanu samo ako ih je
			    bilo u polaznim brojevima */
}

/* Funkcija deli dva neoznacena cela broja u osnovi b. Kolicnik se smesta u q,
   a ostatak pri deljenju u r */
void deljenje(char * x, char * y, unsigned b, char * q, char * r)
{
  char yp[MAX_STR];
  int i;
  unsigned c = 0;
  unsigned nr;
  unsigned d;
  r[0] = '\0';
  q[0] = '\0';
  strcpy(yp, y); /* Koristicemo kopiju yp umesto y, kako ne bismo modifikovali
		    originalni string (postoji mogucnost da ce korisniku
		    funkcije taj string biti i dalje potreban neizmenjen) */
		   
  for(i = 0; x[i] != '\0'; i++)
    {
      nr = strlen(r);      
      r[nr] = x[i];
      r[nr + 1] = '\0'; /* "spustamo" u r sledecu cifru iz x */
      izjednaci_sirine_zapisa(r, yp); /* ...kako bismo mogli da ih oduzimamo */
      c = 0;
      d = 0;
      while(c == 0) /* Brojimo koliko puta mozemo da oduzmemo yp od r */
	{
	  oduzimanje(r, yp, b, r, &c);
	  d++;
	}
      
      /* Ponistavamo poslednje (neuspesno) oduzimanje */
      d--;
      sabiranje(r, yp, b, r, &c);

      /* Upisujemo cifru d na kraj kolicnika q */
      dodaj_k_pratecih_nula(q, 1);	  
      q[strlen(q) - 1] = cifra_u_karakter(d);
    }

  /* Brisemo vodece nule (one mogu nastati prilikom prosirivanja operanada u
     samom algoritmu, cak i ako nisu postojale u originalnim operandima x i y) */     
  obrisi_vodece_nule(q);
  obrisi_vodece_nule(r);
}

/* Funkcija konvertuje zapis iz osnove b1 u osnovu b2, ali ne preko binarnog, vec 
   direktno, koristeci racunske operacije u osnovi b2 (po Hornerovoj shemi) */
void konvertuj_direktno(char * x, unsigned b1, unsigned b2, char * y)
{
  char b1str[MAX_STR];
  char xcstr[MAX_STR];
  char pr[MAX_STR];
  y[0] = '0';
  y[1] = '\0';
  konvertuj_iz_binarnog(b1, b2, b1str);
  int i;
  for(i = 0; x[i] != '\0'; i++)
    {
      unsigned xc = karakter_u_cifru(x[i]);
      konvertuj_iz_binarnog(xc, b2, xcstr);
      mnozenje(y, b1str, b2, pr);
      izjednaci_sirine_zapisa(pr, xcstr);
      prosireno_sabiranje(pr, xcstr, b2, y);
    }
}

int main()
{
  char x[MAX_STR], y[MAX_STR], r[MAX_STR], q[MAX_STR];
  unsigned b, c;
  scanf("%u", &b);
  scanf("%s %s", x, y);
  izjednaci_sirine_zapisa(x, y);
  sabiranje(x, y, b, r, &c);
  printf("%s : %d\n", r, c);
  oduzimanje(x, y, b, r, &c);
  printf("%s : %d\n", r, c);
  mnozenje(x, y, b, r);
  printf("%s\n", r);
  deljenje(x, y, b, q, r);
  printf("%s : %s\n", q, r);
  
  /*  char x[MAX_STR];
  char y[MAX_STR];
  unsigned b1, b2;

  scanf("%d %d", &b1, &b2);
  scanf("%s", x);
  konvertuj_zapis(x, b1, b2, y);
  printf("%s\n", y);
  konvertuj_direktno(x, b1, b2, y);
  printf("%s\n", y);
  */

  return 0;
}