#include <iostream.h>
#include <bool.h>
#define MAXNUM 1001
#define MAXDEN 1001

int nm,dn;

class solgrid {
  public:
    int myval;
    int mynum,myden;
    int num1,num2,den1,den2;
    bool calced;
    bool simplest;
    void init(int nn,int dd);
    void calcmyval();
    void printmyval();
    void printexpr();
    void mirror();
};

solgrid g[MAXNUM][MAXDEN];

int min(int a, int b) {
  if (a < b) return(a);
  else return(b);
}

void solgrid::init(int nn,int dd) {
  calced = false;
  mynum = nn;
  myden = dd;
}

void solgrid::printmyval(void) {
/*  if (!simplest) {
    g[num1][den1].printmyval();
  } else */ if (myden != 1) {
    cout << mynum << "/" << myden << " requires " << myval << " resistors.\n";
  } else {
    cout << mynum << " requires " << myval << " resistors.\n";
  }
}

void solgrid::printexpr(void) {
  if (!simplest) {
    g[num1][den1].printexpr();
  } else if (mynum != myden) {
    if (mynum == num1) {
/*
      cout << mynum << "/" << myden << " = "
           << num1 << "/" << den1 << " * "
           << num2 << "/" << den2 << "\n";
      cout << "[" << mynum << "/" << myden << "]";
      g[num1][den1].printexpr();
      cout << "[" << mynum << "/" << myden << "]";
      g[num2][den2].printexpr();
*/
      cout << "(";
      g[num1][den1].printexpr();
      cout << "*";
      g[num2][den2].printexpr();
      cout << ")"; 
    } else {
/*
      cout << mynum << "/" << myden << " = "
           << num1 << "/" << den1 << " + "
           << num2 << "/" << den2 << "\n";
      cout << "[" << mynum << "/" << myden << "]";
      g[num1][den1].printexpr();
      cout << "[" << mynum << "/" << myden << "]";
      g[num2][den2].printexpr();
*/
      cout << "(";
      g[num1][den1].printexpr();
      cout << "+";
      g[num2][den2].printexpr();
      cout << ")"; 
    }
  } else {
    cout << "1";
  }
}

void solgrid::mirror(void) {
  g[myden][mynum].calced = calced;
  g[myden][mynum].simplest = simplest;
  g[myden][mynum].myval = myval;
  g[myden][mynum].num1 = den1;
  g[myden][mynum].num2 = den2;
  g[myden][mynum].den1 = num1;
  g[myden][mynum].den2 = num2;
}

void solgrid::calcmyval(void) {
  // lcvd > lcvn
  int ld,ln,tval;
  if (!calced) {
    calced = true;
    simplest = true;
    myval = mynum+myden;
    for (ld=1;ld<=myden/2;ld++) {
      tval = g[mynum][ld].myval + g[mynum][myden-ld].myval;
      if (tval < myval) {
        myval = tval;
        num1 = mynum; num2 = mynum;
        den1 = ld; den2 = myden - ld;
      }
    }
    for (ln=1;ln<=mynum/2;ln++) {
      tval = g[ln][myden].myval + g[mynum-ln][myden].myval;
      if (tval < myval) {
        myval = tval;
        num1 = ln; num2 = mynum - ln;
        den1 = myden; den2 = myden;
      }
    }
    for (tval=2;tval<=min((MAXNUM-1)/mynum,(MAXDEN-1)/myden);tval++) {
      g[mynum*tval][myden*tval].calced = true;
      g[mynum*tval][myden*tval].simplest = false;
      g[mynum*tval][myden*tval].myval = myval;
      g[mynum*tval][myden*tval].num1 = mynum;
      g[mynum*tval][myden*tval].den1 = myden;
      if (mynum*tval <= dn && myden*tval <= nm)
        g[mynum*tval][myden*tval].mirror();
    }
  }
  if (mynum <= dn && myden <= nm)
    mirror();
}

void main (void) {
  int lcvn,lcvd;
  cout << "Input numerator (less than MAXNUM):";  
  cin >> nm;
  cout << "Input denominator (less than MAXDEN):";
  cin >> dn;
  for (lcvn=1;lcvn<=nm;lcvn++) for (lcvd=1;lcvd<=dn;lcvd++) 
    g[lcvn][lcvd].init(lcvn,lcvd);

  g[1][1].calced = true;
  g[1][1].myval = 1;
  g[1][1].simplest = true;
  for (lcvn=2;lcvn<=min(nm,dn);lcvn++) {
    g[lcvn][lcvn].calced = true;
    g[lcvn][lcvn].myval = 1;
    g[lcvn][lcvn].simplest = false;
    g[lcvn][lcvn].num1 = 1;
    g[lcvn][lcvn].den1 = 1;
  }

  for (lcvn=1;lcvn<=nm;lcvn++) {
    if (lcvn <= dn)
      cout << "Row " << lcvn << " of " << nm << "\n";
    for (lcvd=lcvn+1;lcvd<=dn;lcvd++) 
    g[lcvn][lcvd].calcmyval();
  }
  for (lcvn=dn+1;lcvn<=nm;lcvn++) {
    cout << "Row " << lcvn << " of " << nm << "\n";
    for (lcvd=1;lcvd<=dn;lcvd++) 
    g[lcvn][lcvd].calcmyval();
  }
  
  g[nm][dn].printmyval();
  g[nm][dn].printexpr();
  cout << "\n";
}