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

struct linked_mpz
{
  struct linked_mpz *previous;
  mpz_t x;
  struct linked_mpz *next;
};

void
toBinary (mpz_t y, int b, mpz_t * x, int n)
{
  mpz_t base;
  mpz_t *xp;
  mpz_init (base);
  mpz_set_ui (base, b);


  xp = (mpz_t *) malloc (sizeof (mpz_t) * n);
  for (int i = 0; i < n; i++)
    {
      mpz_init (xp[i]);
      mpz_set (xp[i], x[i]);
    }


  for (int j = 2; j < n * 2; j += j)
    {
      for (int i = 0; i + j / 2 < n; i += j)
    {
      mpz_mul (xp[i + j / 2], xp[i + j / 2], base);
      mpz_add (xp[i], xp[i], xp[i + j / 2]);
    }
      mpz_mul (base, base, base);
    }
  mpz_set (y, xp[0]);

  for (int i = 0; i < n; i++)
    {
      mpz_clear (xp[i]);
    }
  free (xp);

  mpz_clear (base);
}

int
fromBinary (mpz_t ** y, int b, mpz_t x)
{
  int n;
  struct linked_mpz *powers;
  struct linked_mpz *current_power;
  struct linked_mpz *digits;
  mpz_t *yp;
  powers = (struct linked_mpz *) malloc (sizeof (struct linked_mpz));
  mpz_init (powers->x);
  mpz_set_ui (powers->x, b);
  powers->previous = NULL;

  for (current_power = powers;
       mpz_cmp (x, current_power->x) >= 0;
       current_power = current_power->next)
    {
      struct linked_mpz *power =
    (struct linked_mpz *) malloc (sizeof (struct linked_mpz));
      mpz_init (power->x);
      mpz_mul (power->x, current_power->x, current_power->x);

      power->previous = current_power;
      power->next = NULL;
      current_power->next = power;
    }

  digits = (struct linked_mpz *) malloc (sizeof (struct linked_mpz));
  digits->previous = NULL;
  mpz_set (digits->x, x);
  digits->next = NULL;
  for (current_power = current_power->previous; current_power != NULL;
       current_power = current_power->previous)
    {
      struct linked_mpz *digit = digits;
      mpz_t q;
      mpz_t r;
      mpz_init (q);
      mpz_init (r);
      while (digit != NULL)
    {
      mpz_tdiv_qr (q, r, digit->x, current_power->x);
      mpz_set (digit->x, r);
      if (mpz_cmp_ui (q, 0) > 0)
        {
          struct linked_mpz *next_digit =
        (struct linked_mpz *) malloc (sizeof (struct linked_mpz));
          mpz_init (next_digit->x);
          mpz_set (next_digit->x, q);
          next_digit->previous = digit;
          next_digit->next = digit->next;
          digit->next = next_digit;
          if (next_digit->next != NULL)
        {
          next_digit->next->previous = next_digit;
        }
          digit = next_digit->next;
        }
      else
        {
          digit = digit->next;
        }

    }
      mpz_clear (r);
      mpz_clear (q);
    }

  n = 0;
  for (struct linked_mpz * digit = digits; digit != NULL; digit = digit->next)
    {
      n++;
    }

  yp = malloc (sizeof (mpz_t) * n);
  for (int i = 0; i < n; i++)
    {
      mpz_init (yp[i]);
      mpz_set (yp[i], digits->x);
      mpz_clear (digits->x);
      digits = digits->next;
    }

  *y = yp;

  while (powers != NULL)
    {
      mpz_clear (powers->x);
      powers = powers->next;
    }


  return n;
}

void
factorial (mpz_t x, int n)
{
  mpz_set_ui (x, 1);
  for (int i = 2; i <= n; i++)
    {
      mpz_mul_ui (x, x, i);
    }
}

int
main (int argc, char *argv[])
{
  mpz_t t;
  mpz_t *y;
  mpz_t z;
  int n;
  if (argc <= 1)
    {
      return 0;
    }
  if (atoi (argv[1]) < 1)
    {
      return 0;
    }


  mpz_init (t);
  mpz_init (z);
  factorial (t, atoi (argv[1]));
  n = fromBinary (&y, 10, t);

  for (int i = n - 1; i >= 0; i--)
    {
      gmp_printf ("%Zd", y[i]);
    }
  printf ("\n");

  mpz_init (z);
  toBinary (z, 10, y, n);

  gmp_printf ("%Zd\n", z);

  for (int i = mpz_sizeinbase (z, 2) - 1; i >= 0; i--)
    {
      printf ("%d", mpz_tstbit (z, i));
    }
  printf ("\n");

  for (int i = 0; i < n; i++)
    {
      mpz_clear (y[i]);
    }
  free (y);

  mpz_clear (t);
  mpz_clear (z);

  return 0;
}