import Ġjava . util . TreeMap Ċ import Ġkotlin . math . abs Ċ import Ġkotlin . math . pow Ċ import Ġkotlin . math . sqrt Ċ Ċ private Ġconst Ġval Ġalgorithm Ġ= Ġ 2 Ċ Ċ fun Ġmain () Ġ{ ĊĠĠĠ Ġprintln (" Task Ġ 1 : Ġ Ġcy clo tom ic Ġpolynomial s Ġfor Ġn Ġ<= Ġ 3 0 :") ĊĠĠĠ Ġfor Ġ( i Ġin Ġ 1 .. 3 0 ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġp Ġ= Ġcy clo tom ic Polynomial ( i ) ĊĠĠĠĠĠĠĠ Ġprintln (" CP [$ i ] Ġ= Ġ$ p ") ĊĠĠĠ Ġ} ĊĠĠĠ Ġprintln () ĊĊĠĠĠ Ġprintln (" Task Ġ 2 : Ġ ĠSm allest Ġcy clo tom ic Ġpolynomial Ġwith Ġn Ġor Ġ- n Ġas Ġa Ġcoefficient :") ĊĠĠĠ Ġvar Ġn Ġ= Ġ 0 ĊĠĠĠ Ġfor Ġ( i Ġin Ġ 1 .. 1 0 ) Ġ{ ĊĠĠĠĠĠĠĠ Ġwhile Ġ( true ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġn ++ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġcy clo Ġ= Ġcy clo tom ic Polynomial ( n ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( cy clo !!. has Coefficient Abs ( i )) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġprintln (" CP [$ n ] Ġhas Ġcoefficient Ġwith Ġmagnitude Ġ= Ġ$ i ") ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġn -- ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġbreak ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ } Ċ Ċ private Ġval ĠCOMP UT ED : ĠMutable Map < Int , ĠPol ynomial > Ġ= ĠHashMap () Ċ private Ġfun Ġcy clo tom ic Polynomial ( n : ĠInt ): ĠPol ynomial ? Ġ{ ĊĠĠĠ Ġif Ġ( COMP UT ED . containsKey ( n )) Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn ĠCOMP UT ED [ n ] ĊĠĠĠ Ġ} ĊĠĠĠ Ġif Ġ( n Ġ== Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġ ĠPol ynomial : Ġ Ġx Ġ- Ġ 1 ĊĠĠĠĠĠĠĠ Ġval Ġp Ġ= ĠPol ynomial ( 1 , Ġ 1 , Ġ- 1 , Ġ 0 ) ĊĠĠĠĠĠĠĠ ĠCOMP UT ED [ 1 ] Ġ= Ġp ĊĠĠĠĠĠĠĠ Ġreturn Ġp ĊĠĠĠ Ġ} ĊĠĠĠ Ġval Ġfactors Ġ= Ġget Factors ( n ) ĊĠĠĠ Ġif Ġ( factors . containsKey ( n )) Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġ Ġn Ġprime ĊĠĠĠĠĠĠĠ Ġval Ġterm List : ĠMutable List < Term > Ġ= ĠArrayList () ĊĠĠĠĠĠĠĠ Ġfor Ġ( index Ġin Ġ 0 Ġuntil Ġn ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġterm List . add ( Term ( 1 , Ġindex . to Long ())) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġcy clo Ġ= ĠPol ynomial ( term List ) ĊĠĠĠĠĠĠĠ ĠCOMP UT ED [ n ] Ġ= Ġcy clo ĊĠĠĠĠĠĠĠ Ġreturn Ġcy clo ĊĠĠĠ Ġ} Ġelse Ġif Ġ( factors . size Ġ== Ġ 2 Ġ&& Ġfactors . containsKey ( 2 ) Ġ&& Ġfactors [ 2 ] Ġ== Ġ 1 Ġ&& Ġfactors . containsKey ( n Ġ/ Ġ 2 ) Ġ&& Ġfactors [ n Ġ/ Ġ 2 ] Ġ== Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġ Ġn Ġ= Ġ 2 p ĊĠĠĠĠĠĠĠ Ġval Ġprime Ġ= Ġn Ġ/ Ġ 2 ĊĠĠĠĠĠĠĠ Ġval Ġterm List : ĠMutable List < Term > Ġ= ĠArrayList () ĊĠĠĠĠĠĠĠ Ġvar Ġcoeff Ġ= Ġ- 1 ĊĠĠĠĠĠĠĠ Ġfor Ġ( index Ġin Ġ 0 Ġuntil Ġprime ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcoeff Ġ*= Ġ- 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġterm List . add ( Term ( coeff . to Long (), Ġindex . to Long ())) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġcy clo Ġ= ĠPol ynomial ( term List ) ĊĠĠĠĠĠĠĠ ĠCOMP UT ED [ n ] Ġ= Ġcy clo ĊĠĠĠĠĠĠĠ Ġreturn Ġcy clo ĊĠĠĠ Ġ} Ġelse Ġif Ġ( factors . size Ġ== Ġ 1 Ġ&& Ġfactors . containsKey ( 2 )) Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġ Ġn Ġ= Ġ 2 ^ h ĊĠĠĠĠĠĠĠ Ġval Ġh Ġ= Ġfactors [ 2 ] !! ĊĠĠĠĠĠĠĠ Ġval Ġterm List : ĠMutable List < Term > Ġ= ĠArrayList () ĊĠĠĠĠĠĠĠ Ġterm List . add ( Term ( 1 , Ġ 2 . 0 . pow (( h Ġ- Ġ 1 ). toDouble ()). to Long ())) ĊĠĠĠĠĠĠĠ Ġterm List . add ( Term ( 1 , Ġ 0 )) ĊĠĠĠĠĠĠĠ Ġval Ġcy clo Ġ= ĠPol ynomial ( term List ) ĊĠĠĠĠĠĠĠ ĠCOMP UT ED [ n ] Ġ= Ġcy clo ĊĠĠĠĠĠĠĠ Ġreturn Ġcy clo ĊĠĠĠ Ġ} Ġelse Ġif Ġ( factors . size Ġ== Ġ 1 Ġ&& Ġ! factors . containsKey ( n )) Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġn Ġ= Ġp ^ k ĊĠĠĠĠĠĠĠ Ġvar Ġp Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġfor Ġ( prime Ġin Ġfactors . keys ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġp Ġ= Ġprime ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġk Ġ= Ġfactors [ p ] !! ĊĠĠĠĠĠĠĠ Ġval Ġterm List : ĠMutable List < Term > Ġ= ĠArrayList () ĊĠĠĠĠĠĠĠ Ġfor Ġ( index Ġin Ġ 0 Ġuntil Ġp ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġterm List . add ( Term ( 1 , Ġ( index Ġ* Ġp . toDouble (). pow ( k Ġ- Ġ 1 . toDouble ()). toInt ()). to Long ())) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġcy clo Ġ= ĠPol ynomial ( term List ) ĊĠĠĠĠĠĠĠ ĠCOMP UT ED [ n ] Ġ= Ġcy clo ĊĠĠĠĠĠĠĠ Ġreturn Ġcy clo ĊĠĠĠ Ġ} Ġelse Ġif Ġ( factors . size Ġ== Ġ 2 Ġ&& Ġfactors . containsKey ( 2 )) Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġ Ġn Ġ= Ġ 2 ^ h Ġ* Ġp ^ k ĊĠĠĠĠĠĠĠ Ġvar Ġp Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġfor Ġ( prime Ġin Ġfactors . keys ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( prime Ġ!= Ġ 2 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġp Ġ= Ġprime ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġterm List : ĠMutable List < Term > Ġ= ĠArrayList () ĊĠĠĠĠĠĠĠ Ġvar Ġcoeff Ġ= Ġ- 1 ĊĠĠĠĠĠĠĠ Ġval Ġtwo Exp Ġ= Ġ 2 . 0 . pow (( factors [ 2 ] !! ) Ġ- Ġ 1 . toDouble ()). toInt () ĊĠĠĠĠĠĠĠ Ġval Ġk Ġ= Ġfactors [ p ] !! ĊĠĠĠĠĠĠĠ Ġfor Ġ( index Ġin Ġ 0 Ġuntil Ġp ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcoeff Ġ*= Ġ- 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġterm List . add ( Term ( coeff . to Long (), Ġ( index Ġ* Ġtwo Exp Ġ* Ġp . toDouble (). pow ( k Ġ- Ġ 1 . toDouble ()). toInt ()). to Long ())) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġcy clo Ġ= ĠPol ynomial ( term List ) ĊĠĠĠĠĠĠĠ ĠCOMP UT ED [ n ] Ġ= Ġcy clo ĊĠĠĠĠĠĠĠ Ġreturn Ġcy clo ĊĠĠĠ Ġ} Ġelse Ġif Ġ( factors . containsKey ( 2 ) Ġ&& Ġn Ġ/ Ġ 2 Ġ% Ġ 2 Ġ== Ġ 1 Ġ&& Ġn Ġ/ Ġ 2 Ġ> Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġ ĠCP ( 2 m )[ x ] Ġ= ĠCP (- m )[ x ], Ġn Ġodd Ġinteger Ġ> Ġ 1 ĊĠĠĠĠĠĠĠ Ġval Ġcy clo Div 2 Ġ= Ġcy clo tom ic Polynomial ( n Ġ/ Ġ 2 ) ĊĠĠĠĠĠĠĠ Ġval Ġterm List : ĠMutable List < Term > Ġ= ĠArrayList () ĊĠĠĠĠĠĠĠ Ġfor Ġ( term Ġin Ġcy clo Div 2 !!. pol ynomial Terms ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġterm List . add ( if Ġ( term . exponent Ġ% Ġ 2 Ġ== Ġ 0 L ) Ġterm Ġelse Ġterm . neg ate ()) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġval Ġcy clo Ġ= ĠPol ynomial ( term List ) ĊĠĠĠĠĠĠĠ ĠCOMP UT ED [ n ] Ġ= Ġcy clo ĊĠĠĠĠĠĠĠ Ġreturn Ġcy clo ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġ// Ġ ĠGeneral ĠCase ĊĠĠĠ Ġreturn Ġwhen Ġ( algorithm ) Ġ{ ĊĠĠĠĠĠĠĠĠ 0 Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ ĠS low Ġ- Ġuses Ġbasic Ġdefinition . ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġdiv is ors Ġ= Ġget Div is ors ( n ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ ĠPol ynomial : Ġ Ġ( Ġx ^ n Ġ- Ġ 1 Ġ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġcy clo Ġ= ĠPol ynomial ( 1 , Ġn , Ġ- 1 , Ġ 0 ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġdiv is ors ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġp Ġ= Ġcy clo tom ic Polynomial ( i ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcy clo Ġ= Ġcy clo . divide ( p ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ ĠCOMP UT ED [ n ] Ġ= Ġcy clo ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcy clo ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠ 1 Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ ĠF aster . Ġ ĠRemove ĠMax Ġdivisor Ġ( and Ġall Ġdiv is ors Ġof Ġmax Ġdivisor ) Ġ- Ġonly Ġone Ġdivide Ġfor Ġall Ġdiv is ors Ġof ĠMax ĠDiv isor ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġdiv is ors Ġ= Ġget Div is ors ( n ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġmax Div isor Ġ= ĠInt . MIN _ VALUE ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( div Ġin Ġdiv is ors ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġmax Div isor Ġ= Ġmax Div isor . coerce At Least ( div ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġdiv is ors Except Max : ĠMutable List < Int > Ġ= ĠArrayList () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( div Ġin Ġdiv is ors ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( max Div isor Ġ% Ġdiv Ġ!= Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdiv is ors Except Max . add ( div ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ ĠPol ynomial : Ġ Ġ( Ġx ^ n Ġ- Ġ 1 Ġ) Ġ/ Ġ( Ġx ^ m Ġ- Ġ 1 Ġ), Ġwhere Ġm Ġis Ġthe Ġmax Ġdivisor ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġcy clo Ġ= ĠPol ynomial ( 1 , Ġn , Ġ- 1 , Ġ 0 ). divide ( Polynomial ( 1 , Ġmax Div isor , Ġ- 1 , Ġ 0 )) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġdiv is ors Except Max ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġp Ġ= Ġcy clo tom ic Polynomial ( i ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcy clo Ġ= Ġcy clo . divide ( p ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ ĠCOMP UT ED [ n ] Ġ= Ġcy clo ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcy clo ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠ 2 Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ ĠFast est ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ ĠLet Ġp Ġ; Ġq Ġbe Ġpri mes Ġsuch Ġthat Ġp Ġdoes Ġnot Ġdivide Ġn , Ġand Ġq Ġq Ġdiv ides Ġn . ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ ĠThen ĠCP ( np )[ x ] Ġ= ĠCP ( n )[ x ^ p ] Ġ/ ĠCP ( n )[ x ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġm Ġ= Ġ 1 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġcy clo Ġ= Ġcy clo tom ic Polynomial ( m ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġpri mes Ġ= Ġfactors . keys . to Mutable List () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġpri mes . sort () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( prime Ġin Ġpri mes ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ ĠCP ( m )[ x ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġcy clo M Ġ= Ġcy clo ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ ĠCompute ĠCP ( m )[ x ^ p ]. ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġterm List : ĠMutable List < Term > Ġ= ĠArrayList () ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( t Ġin Ġcy clo M !!. pol ynomial Terms ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġterm List . add ( Term ( t . coefficient , Ġt . exponent Ġ* Ġprime )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcy clo Ġ= ĠPol ynomial ( term List ). divide ( cy clo M ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġm Ġ*= Ġprime ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ ĠNow , Ġm Ġis Ġthe Ġlargest Ġsquare Ġfree Ġdivisor Ġof Ġn ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġs Ġ= Ġn Ġ/ Ġm ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ ĠCompute ĠCP ( n )[ x ] Ġ= ĠCP ( m )[ x ^ s ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġterm List : ĠMutable List < Term > Ġ= ĠArrayList () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( t Ġin Ġcy clo !!. pol ynomial Terms ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġterm List . add ( Term ( t . coefficient , Ġt . exponent Ġ* Ġs )) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcy clo Ġ= ĠPol ynomial ( term List ) ĊĠĠĠĠĠĠĠĠĠĠĠ ĠCOMP UT ED [ n ] Ġ= Ġcy clo ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcy clo ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġelse Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġthrow ĠRuntimeException (" ERROR Ġ 1 0 3 : Ġ ĠInvalid Ġalgorithm .") ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ } Ċ Ċ private Ġfun Ġget Div is ors ( number : ĠInt ): ĠList < Int > Ġ{ ĊĠĠĠ Ġval Ġdiv is ors : ĠMutable List < Int > Ġ= ĠArrayList () ĊĠĠĠ Ġval Ġsqrt Ġ= Ġsqrt ( number . toDouble ()). to Long () ĊĠĠĠ Ġfor Ġ( i Ġin Ġ 1 .. sqrt ) Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( number Ġ% Ġi Ġ== Ġ 0 L ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdiv is ors . add ( i . toInt ()) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġdiv Ġ= Ġ( number Ġ/ Ġi ). toInt () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( div . to Long () Ġ!= Ġi Ġ&& Ġdiv Ġ!= Ġnumber ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġdiv is ors . add ( div ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĠĠĠ Ġreturn Ġdiv is ors Ċ } Ċ Ċ private Ġfun Ġcr utch (): ĠMutable Map < Int , ĠMap < Int , ĠInt >> Ġ{ ĊĠĠĠ Ġval Ġall Factors : ĠMutable Map < Int , ĠMap < Int , ĠInt >> Ġ= ĠTreeMap () ĊĊĠĠĠ Ġval Ġfactors : ĠMutable Map < Int , ĠInt > Ġ= ĠTreeMap () ĊĠĠĠ Ġfactors [ 2 ] Ġ= Ġ 1 ĊĊĠĠĠ Ġall Factors [ 2 ] Ġ= Ġfactors ĊĠĠĠ Ġreturn Ġall Factors Ċ } Ċ Ċ private Ġval Ġall Factors Ġ= Ġcr utch () Ċ Ċ var ĠMAX _ ALL _ FACT ORS Ġ= Ġ 1 0 0 0 0 0 Ċ Ċ fun Ġget Factors ( number : ĠInt ): ĠMap < Int , ĠInt > Ġ{ ĊĠĠĠ Ġif Ġ( all Factors . containsKey ( number )) Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġall Factors [ number ] !! ĊĠĠĠ Ġ} ĊĠĠĠ Ġval Ġfactors : ĠMutable Map < Int , ĠInt > Ġ= ĠTreeMap () ĊĠĠĠ Ġif Ġ( number Ġ% Ġ 2 Ġ== Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġfactors Div Two Ġ= Ġget Factors ( number Ġ/ Ġ 2 ) ĊĠĠĠĠĠĠĠ Ġfactors . put All ( factors Div Two ) ĊĠĠĠĠĠĠĠ Ġfactors . merge ( 2 , Ġ 1 ) Ġ{ Ġa : ĠInt ?, Ġb : ĠInt ? Ġ-> ĠInteger . sum ( a !! , Ġb !! ) Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( number Ġ< ĠMAX _ ALL _ FACT ORS ) Ġall Factors [ number ] Ġ= Ġfactors ĊĠĠĠĠĠĠĠ Ġreturn Ġfactors ĊĠĠĠ Ġ} ĊĠĠĠ Ġval Ġsqrt Ġ= Ġsqrt ( number . toDouble ()). to Long () ĊĠĠĠ Ġvar Ġi Ġ= Ġ 3 ĊĠĠĠ Ġwhile Ġ( i Ġ<= Ġsqrt ) Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( number Ġ% Ġi Ġ== Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfactors . put All ( get Factors ( number Ġ/ Ġi )) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfactors . merge ( i , Ġ 1 ) Ġ{ Ġa : ĠInt ?, Ġb : ĠInt ? Ġ-> ĠInteger . sum ( a !! , Ġb !! ) Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( number Ġ< ĠMAX _ ALL _ FACT ORS ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġall Factors [ number ] Ġ= Ġfactors ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġfactors ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġi Ġ+= Ġ 2 ĊĠĠĠ Ġ} ĊĠĠĠ Ġfactors [ number ] Ġ= Ġ 1 ĊĠĠĠ Ġif Ġ( number Ġ< ĠMAX _ ALL _ FACT ORS ) Ġ{ ĊĠĠĠĠĠĠĠ Ġall Factors [ number ] Ġ= Ġfactors ĊĠĠĠ Ġ} ĊĠĠĠ Ġreturn Ġfactors Ċ } Ċ Ċ private Ġclass ĠPol ynomial Ġ{ ĊĠĠĠ Ġval Ġpolynomial Terms : ĠMutable List < Term > ĊĊĠĠĠ Ġ// Ġ ĠFormat Ġ- Ġcoeff , Ġexp , Ġcoeff , Ġexp , Ġ( repe ating Ġin Ġpairs ) Ġ. Ġ. Ġ. ĊĠĠĠ Ġconstructor ( var arg Ġvalues : ĠInt ) Ġ{ ĊĠĠĠĠĠĠĠ Ġrequire ( values . size Ġ% Ġ 2 Ġ== Ġ 0 ) Ġ{ Ġ" ERROR Ġ 1 0 2 : Ġ ĠPol ynomial Ġconstructor . Ġ ĠLength Ġmust Ġbe Ġeven . Ġ ĠLength Ġ= Ġ" Ġ+ Ġvalues . size Ġ} ĊĠĠĠĠĠĠĠ Ġpolynomial Terms Ġ= Ġmutable ListOf () ĊĠĠĠĠĠĠĠ Ġvar Ġi Ġ= Ġ 0 ĊĠĠĠĠĠĠĠ Ġwhile Ġ( i Ġ< Ġvalues . size ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġt Ġ= ĠTerm ( values [ i ]. to Long (), Ġvalues [ i Ġ+ Ġ 1 ]. to Long ()) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġpolynomial Terms . add ( t ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġi Ġ+= Ġ 2 ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġpolynomial Terms . sort With ( Term Sorter ()) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġconstructor () Ġ{ ĊĠĠĠĠĠĠĠ Ġ// Ġ Ġzero ĊĠĠĠĠĠĠĠ Ġpolynomial Terms Ġ= ĠArrayList () ĊĠĠĠĠĠĠĠ Ġpolynomial Terms . add ( Term ( 0 , Ġ 0 )) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġhas Coefficient Abs ( coeff : ĠInt ): ĠBoolean Ġ{ ĊĠĠĠĠĠĠĠ Ġfor Ġ( term Ġin Ġpolynomial Terms ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( abs ( term . coefficient ) Ġ== Ġcoeff . to Long ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġfalse ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġconstructor ( term List : ĠMutable List < Term >) Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( term List . isEmpty ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ Ġzero ĊĠĠĠĠĠĠĠĠĠĠĠ Ġterm List . add ( Term ( 0 , Ġ 0 )) ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ ĠRemove Ġzero Ġterms Ġif Ġneeded ĊĠĠĠĠĠĠĠĠĠĠĠ Ġterm List . remove If Ġ{ Ġt Ġ-> Ġt . coefficient Ġ== Ġ 0 L Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( term List . size Ġ== Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ Ġzero ĊĠĠĠĠĠĠĠĠĠĠĠ Ġterm List . add ( Term ( 0 , Ġ 0 )) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġpolynomial Terms Ġ= Ġterm List ĊĠĠĠĠĠĠĠ Ġpolynomial Terms . sort With ( Term Sorter ()) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġdivide ( v : ĠPol ynomial ?): ĠPol ynomial Ġ{ ĊĠĠĠĠĠĠĠ Ġvar Ġq Ġ= ĠPol ynomial () ĊĠĠĠĠĠĠĠ Ġvar Ġr Ġ= Ġthis ĊĠĠĠĠĠĠĠ Ġval Ġl cv Ġ= Ġv !!. leading Coefficient () ĊĠĠĠĠĠĠĠ Ġval Ġdv Ġ= Ġv . degree () ĊĠĠĠĠĠĠĠ Ġwhile Ġ( r . degree () Ġ>= Ġv . degree ()) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġl cr Ġ= Ġr . leading Coefficient () ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġs Ġ= Ġl cr Ġ/ Ġl cv Ġ// Ġ ĠInteger Ġdivision ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġterm Ġ= ĠTerm ( s , Ġr . degree () Ġ- Ġdv ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġq Ġ= Ġq . add ( term ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġr Ġ= Ġr . add ( v . multiply ( term . neg ate ())) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġq ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġadd ( pol ynomial : ĠPol ynomial ): ĠPol ynomial Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġterm List : ĠMutable List < Term > Ġ= ĠArrayList () ĊĠĠĠĠĠĠĠ Ġvar Ġthis Count Ġ= Ġpolynomial Terms . size ĊĠĠĠĠĠĠĠ Ġvar Ġpoly Count Ġ= Ġpolynomial . pol ynomial Terms . size ĊĠĠĠĠĠĠĠ Ġwhile Ġ( this Count Ġ> Ġ 0 Ġ|| Ġpoly Count Ġ> Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġthis Term Ġ= Ġif Ġ( this Count Ġ== Ġ 0 ) Ġnull Ġelse Ġpolynomial Terms [ this Count Ġ- Ġ 1 ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġpoly Term Ġ= Ġif Ġ( poly Count Ġ== Ġ 0 ) Ġnull Ġelse Ġpolynomial . pol ynomial Terms [ poly Count Ġ- Ġ 1 ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġwhen Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġthis Term Ġ== Ġnull Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġterm List . add ( poly Term !!. clone ()) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġpoly Count -- ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġpoly Term Ġ== Ġnull Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġterm List . add ( this Term . clone ()) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġthis Count -- ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġthis Term . degree () Ġ== Ġpoly Term . degree () Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġt Ġ= Ġthis Term . add ( poly Term ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( t . coefficient Ġ!= Ġ 0 L ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġterm List . add ( t ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġthis Count -- ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġpoly Count -- ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġthis Term . degree () Ġ< Ġpoly Term . degree () Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġterm List . add ( this Term . clone ()) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġthis Count -- ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġelse Ġ-> Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġterm List . add ( poly Term . clone ()) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġpoly Count -- ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn ĠPol ynomial ( term List ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġadd ( term : ĠTerm ): ĠPol ynomial Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġterm List : ĠMutable List < Term > Ġ= ĠArrayList () ĊĠĠĠĠĠĠĠ Ġvar Ġadded Ġ= Ġfalse ĊĠĠĠĠĠĠĠ Ġfor Ġ( current Term Ġin Ġpolynomial Terms ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( current Term . exponent Ġ== Ġterm . exponent ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġadded Ġ= Ġtrue ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( current Term . coefficient Ġ+ Ġterm . coefficient Ġ!= Ġ 0 L ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġterm List . add ( current Term . add ( term )) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġterm List . add ( current Term . clone ()) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ(! added ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġterm List . add ( term . clone ()) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn ĠPol ynomial ( term List ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġmultiply ( term : ĠTerm ): ĠPol ynomial Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġterm List : ĠMutable List < Term > Ġ= ĠArrayList () ĊĠĠĠĠĠĠĠ Ġfor Ġ( current Term Ġin Ġpolynomial Terms ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġterm List . add ( current Term . clone (). multiply ( term )) ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn ĠPol ynomial ( term List ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġleading Coefficient (): ĠLong Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġpolynomial Terms [ 0 ]. coefficient ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġdegree (): ĠLong Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġpolynomial Terms [ 0 ]. exponent ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun ĠtoString (): ĠString Ġ{ ĊĠĠĠĠĠĠĠ Ġval Ġsb Ġ= ĠStringBuilder () ĊĠĠĠĠĠĠĠ Ġvar Ġfirst Ġ= Ġtrue ĊĠĠĠĠĠĠĠ Ġfor Ġ( term Ġin Ġpolynomial Terms ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( first ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġsb . append ( term ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfirst Ġ= Ġfalse ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġsb . append (" Ġ") ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( term . coefficient Ġ> Ġ 0 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġsb . append ("+ Ġ") ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġsb . append ( term ) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġsb . append ("- Ġ") ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġsb . append ( term . neg ate ()) ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġsb . toString () ĊĠĠĠ Ġ} Ċ } Ċ Ċ private Ġclass ĠTerm Sorter Ġ: ĠComparator < Term > Ġ{ ĊĠĠĠ Ġoverride Ġfun Ġcompare ( o 1 : ĠTerm , Ġo 2 : ĠTerm ): ĠInt Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġ( o 2 . exponent Ġ- Ġo 1 . exponent ). toInt () ĊĠĠĠ Ġ} Ċ } Ċ Ċ // Ġ ĠNote : Ġ ĠCy clo tom ic ĠPol ynomial s Ġhave Ġsmall Ġcoefficients . Ġ ĠNot Ġappropriate Ġfor Ġgeneral Ġpolynomial Ġusage . Ċ private Ġclass ĠTerm ( var Ġcoefficient : ĠLong , Ġvar Ġexponent : ĠLong ) Ġ{ ĊĠĠĠ Ġfun Ġclone (): ĠTerm Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn ĠTerm ( coefficient , Ġexponent ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġmultiply ( term : ĠTerm ): ĠTerm Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn ĠTerm ( coefficient Ġ* Ġterm . coefficient , Ġexponent Ġ+ Ġterm . exponent ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġadd ( term : ĠTerm ): ĠTerm Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( exponent Ġ!= Ġterm . exponent ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġthrow ĠRuntimeException (" ERROR Ġ 1 0 2 : Ġ ĠExp onent s Ġnot Ġequal .") ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn ĠTerm ( coefficient Ġ+ Ġterm . coefficient , Ġexponent ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġneg ate (): ĠTerm Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn ĠTerm (- coefficient , Ġexponent ) ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġdegree (): ĠLong Ġ{ ĊĠĠĠĠĠĠĠ Ġreturn Ġexponent ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġoverride Ġfun ĠtoString (): ĠString Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( coefficient Ġ== Ġ 0 L ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġ" 0 " ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( exponent Ġ== Ġ 0 L ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġ"" Ġ+ Ġcoefficient ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġif Ġ( coefficient Ġ== Ġ 1 L ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn Ġif Ġ( exponent Ġ== Ġ 1 L ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ" x " ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ" x ^ $ exponent " ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġreturn Ġif Ġ( exponent Ġ== Ġ 1 L ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġcoefficient . toString () Ġ+ Ġ" x " ĊĠĠĠĠĠĠĠ Ġ} Ġelse Ġcoefficient . toString () Ġ+ Ġ" x ^ " Ġ+ Ġexponent ĊĠĠĠ Ġ} Ċ } Ċ