Problem A
Hrópmerkingardulkóðun

Mynd eftir Jahnke og Emde, commons.wikimedia.org

Til er (opin) tilgáta sem segir að fyrir frumtölu $p$ og $0 < x < p$ séu ávallt til tvær tölur $0 \leq a, b < p$ þannig að $x \equiv a!b! \pmod{p}$.

Þú rakst á ritgerð sem talaði um að nota þetta til dulkóðunar. Þá væri hugmyndin að allir vissu $x, p$, en $a, b$ væri leynileg. Þú bendir höfundunum vinsamlegast á það að ef $p > 10^{12}$ eða svo væri ófýsilegt að reikna út $a!$ og $b!$ í skikkanlegum tíma. Eftir að þeir svara að þá sé bara hægt að hafa $p \leq 10^{12}$ viltu samt ennþá sýna að þetta sé slæm hugmynd.

Besta leiðin til þess er auðvitað að útbúa forrit sem tekur inn $x, p$ og prentar þessi leynilegu $a, b$!¹

Athugið að af tæknilegum ástæðum er þetta verkefni keyrt gagnvirkt. Það þýðir að ef þið reynið að lesa meira inntak en er til staðar gæti forrit ykkar hangið og þið farið yfir tímamörk. Athugið þess vegna að passa að sturta úr úttaksbiðminni.

Inntak

Fyrsta og eina línan inniheldur tvær heiltölur $x, p$ aðskildar með bili sem uppfylla $0 < x < p$ og $1 \leq p \leq 10^{12}$. Enn fremur er $p$ ávallt frumtala.

Úttak

Prentið tvær tölur $0 \leq a, b < p$ aðskildar með bili þannig að $x \equiv a!b! \pmod{p}$. Ef til er fleiri en eitt rétt svar verður hvert sem er þeirra samþykkt.

Útskýring á sýnidæmi

Í fyrra sýnidæminu er $x = 6$ og $p = 101$. Það eru margar lausnir, en ein þeirra er $a = 0$ og $b = 3$. Þá er $a! = 1$ og $b! = 6$ svo $a!b! = 6$. Annar valkostur er að taka $a = 16$ og $b = 4$. Þá er $a! = 20922789888000$ og $b! = 24$. Þar með er $a!b! = 502146957312000$ sem gefur einmitt afgang $6$ þegar því er deilt með $101$.

6 101

0 3

101 999983

44758 144580