Problem D
Logri
Languages
en
is
Þú og vinur þinn eigið öll ykkar samskipti með sendibréfum. Nú ert þú orðinn leiður á hversu gamaldags þetta ferli er. Til að númtímavæða samskiptin ykkar langar þig að innleiða dulkóðun í samskiptaferlið.
Hluti af því að dulkóða samskiptinni ykkar verður að skiptast á dulkóðunarlyklum. Til þess ætlið þið að nota Diffie-Hellman aðferðina. Aðferðin byggir á því að það er erfitt að leysa jöfnuna
\begin{equation*} a^ x = b \mod m \end{equation*}fyrir $x$. Lausn á þessari jöfnu kallast strjáll logri tölunnar $b$ með grunn $a$ með tilliti til $m$. Til þess að þetta sé erfitt þarf $m - 1$ af hafa stóran frumþátt. Við segjum því að öryggisstuðull tölurnnar $m$ sé stærsti frumþáttur tölunnar $m - 1$.
Nú er vinur þinn búinn að gefa þér lista af tölum og þig langar að reikna öryggisstuðul talnanna, til að finna hver þeirra er öruggust.
Inntak
Eina lína inntaksins inniheldur eina heiltölu $m$ ($1 \leq m \leq 10^{18}$).
Úttak
Úttakið skal innihalda eina heiltölu, öryggisstuðul tölunnar $m$.
| Sample Input 1 | Sample Output 1 |
|---|---|
23 |
11 |
| Sample Input 2 | Sample Output 2 |
|---|---|
32 |
31 |
| Sample Input 3 | Sample Output 3 |
|---|---|
999999866000004474 |
999999937 |
| Sample Input 4 | Sample Output 4 |
|---|---|
576460752303423489 |
2 |
