rendered paste body<?phpclass Monomial { var $numeric_factor = 1; var $vars = array(); // 5a^2, n_f = 5, vars = array('a' => 2); function mul(Monomial $b, $is_div = false) { $nf = $is_div ? ($this->numeric_factor / $b->numeric_factor) : ($this->numeric_factor * $b->numeric_factor); $nv = array(); foreach($this->vars as $var => $exp) { if(isset($b->vars[$var])) { if($is_div) { $nv[$var] = $exp - $b->vars[$var]; } else { $nv[$var] = $exp + $b->vars[$var]; } } else { $nv[$var] = $exp; } } foreach($b->vars as $var => $exp) { if(!isset($nv[$var])) { if($is_div) { throw new Exception('Illegal monomial division'); } else { $nv[$var] = $exp; } } } $this->numeric_factor = $nf; $this->vars = $nv; $this->cleanup(); } function mulf(Monomial $b, $is_div = false) { $m = clone $this; $m->mul($b, $is_div); return $m; } function div(Monomial $b) { $this->mul($b, true); $this->cleanup(); } function divf(Monomial $b) { return mulf($b, true); } function remove_var_1($res) { $v = $res[1]; $n = $res[2]; if(!isset($this->vars[$v])) $this->vars[$v] = 0; $this->vars[$v] += $n; } function remove_var_2($res) { $this->remove_var_1(array(0, $res[0], 1)); } function Monomial($str='') { $str = preg_replace('/\s/', '', $str); $str = preg_replace_callback('/([a-z])\^([0-9]+)/i', array($this, 'remove_var_1'), $str); $str = preg_replace_callback('/[a-z]/i', array($this, 'remove_var_2'), $str); $str = trim($str); if(is_numeric($str)) { $this->numeric_factor = (real) $str; } else if($str == '') { $this->numeric_factor = 1; } else { throw new InvalidArgumentException('Nonnumeric final string ' . $str); } } function cleanup() { // get rid of the ones is all we need to do here foreach($this->vars as $var => $exp) { if($exp == 0) unset($this->vars[$var]); } if($this->numeric_factor == 0) $this->vars = array(); // 0 cancels it out :) } function to_str() { $str = (string) $this->numeric_factor; if($str == '1' && count($this->vars) > 0) $str = ''; foreach($this->vars as $v => $e) { if($e == 1) { $str .= $v; } else { $str .= "$v^$e"; } } return $str; }}class Polynomial { var $mos = array(); function Polynomial($str='') { $str = trim($str); if($str != '') { $str = preg_replace('/\s/', '', $str); $str = str_replace('-', '+-', $str); $str = str_replace('++', '+', $str); $str = str_replace('--', '', $str); $str = explode('+', $str); foreach($str as &$part) { $part = new Monomial($part); } $this->mos = $str; } $this->cleanup(); } function add($b) { if($b instanceof Monomial) { $this->mos[] = clone $b; } else if($b instanceof Polynomial) { foreach($b->mos as $mo) { $this->mos[] = clone $mo; } } else { throw new Exception('Polynomial::add() doesn\'t understand a b of type ' . get_class($b)); } $this->cleanup(); } function sub($b) { $b = clone $b; if($b instanceof Monomial) { $b->numeric_factor = -($b->numeric_factor); } else if($b instanceof Polynomial) { foreach($b->mos as $mo) { $mo->numeric_factor = -($mo->numeric_factor); } } else { throw new Exception('Polynomial::sub() doesn\'t understand a b of type ' . get_class($b)); } $this->add($b); } function div(Monomial $b) { foreach($this->mos as $mo) { $mo->div($b); } $this->cleanup(); } function mul($b) { $newmos = array(); if($b instanceof Monomial) { foreach($this->mos as $mo) { $moc = clone $mo; $moc->mul($b); $newmos[] = $moc; } } else if($b instanceof Polynomial) { foreach($this->mos as $mo1) { foreach($b->mos as $mo2) { $moc = clone $mo1; $moc->mul($mo2); $newmos[] = $moc; } } } else { throw new Exception('Polynomial::mul() doesn\'t understand a b of type ' . get_class($b)); } $this->mos = $newmos; $this->cleanup(); } function to_str() { $mos = $this->mos; $first = array_shift($mos); $str = $first->to_str(); foreach($mos as $mo) { if($mo->numeric_factor < 0) { $moc = clone $mo; $moc->numeric_factor = abs($moc->numeric_factor); $str .= ' - ' . $moc->to_str(); } else { $str .= ' + ' . $mo->to_str(); } } return $str; } function cleanup() { foreach($this->mos as $mo1) { foreach($this->mos as $k => $mo2) { if($mo1 !== $mo2 && $mo1->vars == $mo2->vars) { $mo1->numeric_factor += $mo2->numeric_factor; $mo1->cleanup(); $mo2->numeric_factor = 0; break; } } } foreach($this->mos as $k => $mo) { if($mo->numeric_factor == 0) unset($this->mos[$k]); } }}function simplefactor(Polynomial $p) { // accepts a polynomial // returns array('mono' => a Monomial, 'poly' => a Polynomial, 'str' => string representation) // the monomial should be the GCF of the polynomial $mos = /* copy */ $p->mos; $gcf = new Monomial; $mo = array_shift($mos); $gcf->vars = $mo->vars; foreach($mos as $mo) { foreach($gcf->vars as $var => &$exp) { if(!isset($mo->vars[$var])) unset($gcf->vars[$var]); elseif($exp > $mo->vars[$var]) $exp = $mo->vars[$var]; } } // okay, now for numbers $mos = $p->mos; // re the first one $is_all_same = $mos[0]->numeric_factor; $is_all_int = true; foreach($mos as $mo) { if($mo->numeric_factor != $is_all_same) $is_all_same = FALSE; if($mo->numeric_factor != (int) $mo->numeric_factor) $is_all_int = FALSE; } if($is_all_same !== FALSE) { $gcf->numeric_factor = $is_all_same; } else if($is_all_int) { $nfs = array(); foreach($mos as $mo) { $nfs[] = $mo->numeric_factor; } // gcf function $cfs = array(); for($g = 1; $g <= max($nfs); $g++) { $is_cf = true; foreach($nfs as $nf) { $nfg = $nf / $g; if($nfg != (int) $nfg) $is_cf = false; } if($is_cf) $cfs[] = $g; } if(count($cfs) != 0) $gcf->numeric_factor = max($cfs); // GCF } $pc = clone $p; foreach($pc->mos as &$mo) { $mo = clone $mo; // deep clone $mo->div($gcf); } return array('mono' => $gcf, 'poly' => $pc, 'str' => $gcf->to_str() . '(' . $pc->to_str() . ')');}while($line = trim(fgets(STDIN))) { echo "$line\n"; try { $p = new Polynomial($line); } catch(InvalidArgumentException $e) { echo "Invalid string\n"; continue; } $p = simplefactor(new Polynomial($line)); echo $p['str'] . "\n";}?>