package Ġsolved Ċ Ċ import Ġtasks . Abstract Task Ċ import Ġtasks . Tester Ċ import Ġutils . My Math Ċ import Ġutils . log . Logger Ċ Ċ // Answer Ġ: Ġ 3 5 5 7 0 0 5 2 6 1 9 0 6 2 8 8 Ċ class ĠTask _ 5 3 6 Ġ: ĠAbstract Task () Ġ{ ĊĠĠĠ Ġval ĠL IM Ġ= Ġ 1 0 0 0 0 0 0 L ; Ċ // ĠĠĠ Ġval ĠL IM Ġ= Ġ 1 0 0 0 0 0 0 0 0 0 0 0 0 L ; ĊĊĠĠĠ Ġvar Ġsum Ġ= Ġ 1 1 L ; ĊĠĠĠ Ġvar Ġmax prime Ġ= Ġ 0 L ; ĊĠĠĠ Ġvar Ġpri mes : ĠLong Array Ġ= ĠLong Array ( 0 ); ĊĠĠĠ Ġvar Ġfactors : ĠLong Array Ġ= ĠLong Array ( 0 ); ĊĠĠĠ Ġvar Ġis Prime : ĠBoolean Array Ġ= ĠBoolean Array ( 0 ); ĊĊĠĠĠ Ġoverride Ġfun Ġsolving () Ġ{ ĊĠĠĠĠĠĠĠ ĠMy Math . setMax Pri mes To Cache ( 8 0 0 0 0 ); ĊĠĠĠĠĠĠĠ Ġpri mes Ġ= ĠMy Math . get Pri mes Between ( 0 , ĠMath . sqrt (( LIM Ġ+ Ġ 4 ). toDouble ()). to Long () Ġ+ Ġ 3 L ) ĊĠĠĠĠĠĠĠ Ġmax prime Ġ= Ġpri mes . last () ĊĊĠĠĠĠĠĠĠ Ġfactors Ġ= ĠLong Array ( pri mes . size ); ĊĠĠĠĠĠĠĠ Ġis Prime Ġ= ĠBoolean Array ( max prime . toInt () Ġ+ Ġ 1 ) ĊĊĠĠĠĠĠĠĠ Ġfor Ġ( p Ġin Ġpri mes ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġis Prime [ p . toInt ()] Ġ= Ġtrue ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġprintln (" go ") ĊĊĠĠĠĠĠĠĠ Ġfind ( 0 , Ġ 1 , Ġ 1 L ) ĊĊĠĠĠĠĠĠĠ Ġprintln ( sum ); ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġfun Ġfind ( fact Ind : ĠInt , Ġind : ĠInt , Ġn : ĠLong ) Ġ{ ĊĠĠĠĠĠĠĠ Ġif Ġ( ind Ġ== Ġpri mes . size ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġreturn ; ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġif Ġ( fact Ind Ġ> Ġ 0 ) Ġ{ ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġsolving Ġn * x Ġâī ¡ Ġ- 3 Ġ( mod Ġq - 1 ), Ġq Ġis Ġlargest Ġfactor , Ġthan Ġx Ġis Ġthe Ġnext Ġfactor ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ 1 st Ġcase Ġ 3 ! | n Ġand Ġ 3 ! | q - 1 Ġ=> Ġn Ġ* Ġx Ġ- Ġk Ġ* Ġ( q - 1 ) Ġ= Ġ- 3 ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġ 2 nd Ġcase Ġ 3 | n Ġand Ġ 3 | q - 1 Ġ=> Ġ( n / 3 )* x Ġ- Ġk *( q - 1 )/ 3 Ġ= Ġ- 1 ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġx : ĠLong ; ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġg : ĠLong ; ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġlast Factor Ġ= Ġfactors [ fact Ind Ġ- Ġ 1 ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġq Ġ= Ġlast Factor Ġ- Ġ 1 ; ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( n Ġ% Ġ 3 Ġ== Ġ 0 L Ġ&& Ġq Ġ% Ġ 3 Ġ== Ġ 0 L ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġx Ġ= Ġ-( n / 3 )^ (- 1 ) Ġ( mod Ġ( q - 1 )/ 3 ), Ġn % 3 Ġ== Ġ 0 Ġ&& Ġq - 1 Ġ% Ġ 3 Ġ== Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġq Ġ/= Ġ 3 ; ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġrr Ġ= ĠMy Math . mod Inverse With Rem ( n Ġ/ Ġ 3 Ġ% Ġq , Ġq ); ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġx Ġ= Ġq Ġ- Ġrr [ 1 ] ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġg Ġ= Ġrr [ 0 ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} Ġelse Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġx Ġ= Ġ- 3 * n ^ (- 1 ) Ġ( mod Ġq - 1 ), Ġn % 3 Ġ!= Ġ 0 Ġ|| Ġq - 1 Ġ% Ġ 3 Ġ!= Ġ 0 ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġrr Ġ= ĠMy Math . mod Inverse With Rem ( n Ġ% Ġq , Ġq ); ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġx Ġ= Ġ( q Ġ- Ġ 3 ) Ġ* Ġrr [ 1 ] Ġ% Ġq ; ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġg Ġ= Ġrr [ 0 ] ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( g Ġ== Ġ 1 L ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġso Ġpossible Ġfuture Ġnumbers Ġare Ġnn Ġ= Ġx Ġ+ Ġk Ġ* Ġq ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġbut Ġalso Ġnn Ġ= Ġn Ġ* Ġprime , Ġand Ġprime Ġ> Ġlast Factor ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġfind Ġmin Ġcandidate ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġmin prime Ġ= Ġpri mes [ ind ]; ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġcandidate Ġ= Ġmin prime Ġ/ Ġq Ġ* Ġq Ġ+ Ġx ; ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( candidate Ġ< Ġmin prime ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcandidate Ġ+= Ġq ; ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġnn Ġ= Ġn Ġ* Ġcandidate ; ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ ĠTOP @ Ġwhile Ġ( nn Ġ<= ĠL IM Ġ&& Ġcandidate Ġ<= Ġmax prime ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( is Prime [ candidate . toInt ()]) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(( nn Ġ+ Ġ 3 ) Ġ% Ġ( candidate Ġ- Ġ 1 ) Ġ!= Ġ 0 L ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcandidate Ġ+= Ġq ; ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnn Ġ= Ġn Ġ* Ġcandidate ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcontinue ; ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġ 0 .. fact Ind Ġ- Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ(( nn Ġ+ Ġ 3 ) Ġ% Ġ( factors [ i ] Ġ- Ġ 1 ) Ġ!= Ġ 0 L ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcandidate Ġ+= Ġq ; ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnn Ġ= Ġn Ġ* Ġcandidate ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcontinue @ TOP ; ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġsum Ġ+= Ġnn ; ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġcandidate Ġ+= Ġq ; ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġnn Ġ= Ġn Ġ* Ġcandidate ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġind .. pri mes . size Ġ- Ġ 1 ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġprime Ġ= Ġpri mes [ i ]; ĊĠĠĠĠĠĠĠĠĠĠĠ Ġvar Ġnn Ġ= Ġn Ġ* Ġprime ; ĊĠĠĠĠĠĠĠĠĠĠĠ Ġif Ġ( nn Ġ* Ġprime Ġ> ĠL IM ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġbreak ; ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġfactors [ fact Ind ] Ġ= Ġprime ; ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfind ( fact Ind Ġ+ Ġ 1 , Ġi Ġ+ Ġ 1 , Ġnn ); ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} ĊĊĠĠĠ Ġcompanion Ġobject Ġ{ ĊĠĠĠĠĠĠĠ Ġ@ Jvm Static Ġfun Ġmain ( args : ĠArray < String >) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠ ĠLogger . init (" default . log ") ĊĠĠĠĠĠĠĠĠĠĠĠ ĠTest er . test ( Task _ 5 3 6 ()) ĊĠĠĠĠĠĠĠĠĠĠĠ ĠLogger . close () ĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ } Ċ