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

#define MAX 100

typedef struct {
   int numerator, denominator;
} rational;

typedef struct {
   int degree;
   int coefficient[MAX];
} polynomial;

typedef struct {
   int nfactors;
   int factor[MAX];
} factorlist;

int gcd ( int a, int b )
{
   int r;

   if ((a == 0) && (b == 0)) return 0;
   if (a < 0) a = -a;
   if (b < 0) b = -b;
   while (b) {
      r = a % b;
      a = b;
      b = r;
   }
   return a;
}

rational reduce ( rational x )
{
   int d;

   d = gcd(x.numerator,x.denominator);
   if (d > 0) {
      x.numerator /= d;
      x.denominator /= d;
   }
   return x;
}

rational radd ( rational x, rational y )
{
   rational z;

   z.numerator = (x.numerator)*(y.denominator) + (x.denominator)*(y.numerator);
   z.denominator = (x.denominator)*(y.denominator);
   return reduce(z);
}

rational rmul ( rational x, rational y )
{
   rational z;

   z.numerator = (x.numerator)*(y.numerator);
   z.denominator = (x.denominator)*(y.denominator);
   return reduce(z);
}

rational evalpoly ( polynomial f, rational x )
{
   int i;
   rational sum, xpower, term;

   if (f.degree < 0) return (rational){0,1};
   sum.numerator = f.coefficient[0]; sum.denominator = 1;
   xpower = (rational){1,1};
   for (i=1; i<=f.degree; ++i) {
      xpower = rmul(xpower,x);
      term = rmul(xpower,(rational){f.coefficient[i],1});
      sum = radd(sum,term);
   }
   return reduce(sum);
}

factorlist getfactors ( int n )
{
   factorlist L;
   int d;

   if (n == 0) { L.nfactors = 0; return L; }
   if (n < 0) n = -n;
   L.nfactors = 0;
   for (d=1; d<=n; ++d) {
      if (n % d == 0) L.factor[L.nfactors++] = d;
   }
   return L;
}

void findroots ( polynomial f )
{
   int i,j,d;
   rational x, fx;
   factorlist L1, L2;

   if (f.degree <= 0) return;
   L1 = getfactors(f.coefficient[0]);
   L2 = getfactors(f.coefficient[f.degree]);
   for (i=0; i<L1.nfactors; ++i) for (j=0; j<L2.nfactors; ++j) {
      x.numerator = L1.factor[i];
      x.denominator = L2.factor[j];
      d = gcd(x.numerator,x.denominator);
      if (d == 1) {
         fx = evalpoly(f,x);
         if (fx.numerator == 0)
            printf("Root found: %d/%d\n", x.numerator, x.denominator);
         x.numerator = -x.numerator;
         fx = evalpoly(f,x);
         if (fx.numerator == 0)
            printf("Root found: %d/%d\n", x.numerator, x.denominator);
      }
   }
}

int main ()
{
   polynomial f;

   printf("\nPolynomial 1: 120x^4 + 14x^3 - 113x^2 - 10x + 24\n");
   f.degree = 4;
   f.coefficient[4] = 120;
   f.coefficient[3] = 14;
   f.coefficient[2] = -113;
   f.coefficient[1] = -10;
   f.coefficient[0] = 24;
   findroots(f);

   printf("\nPolynomial 2: 24x^6 + 46x^5 + 33x^4 + x^3 - 18x^2 - 5x + 3\n");
   f.degree = 6;
   f.coefficient[6] = 24;
   f.coefficient[5] = 46;
   f.coefficient[4] = 33;
   f.coefficient[3] = 1;
   f.coefficient[2] = -18;
   f.coefficient[1] = -5;
   f.coefficient[0] = 3;
   findroots(f);

   exit(0);
}