== include(page="template/taskheader" task_id="voodoo") ==
Poveste şi cerinţă...
Georgian lucra la un proiect Voodoo, până când i-a venit în cap o problemă ezoterică cu nişte funcţii la fel de ezoterice.
Fie un număr $x$, căruia vrem să îi calculăm cifra de control în baza $B$. Aceasta se poate calcula folosind următorul algoritm:
==code(c) |
// vrem să calculăm cifra de control a lui x în baza B.
int cfcontrol(int x, int B) {
while(x >= B) // Atâta timp cât x are două sau mai multe cifre în baza B.
x = sumcf(x, B); // Înlocuim pe x cu suma cifrelor sale în baza B. (*)
return x; // Rezultatul final va fi valoarea stocată în variabila x.
}
// Notă: Numerele pot ajunge foarte mari. Vom presupune aici că tipul de date int poate stoca numere oricât de mari, nu doar până la 2^31 - 1.
==
Se definesc următoarele două funcţii $F{~B~}$ şi $G{~B~}$.
$F{~B~}(n)$ va fi numărul de dăţi în care se calculeză suma cifrelor în apelul funcţiei $cfcontrol(n, B)$, adică de câte ori se execută linia a 4-a din program (marcată cu $(*)$).
$G{~B~}(n) = x$ unde $x$ este cel mai mic număr natural nenul în care $F{~B~}(x) = n$.
În următorul tabel sunt prezentate mai multe exemple de calcul al cifrei de control şi al funcţiei F{~B~}.
table(cfcontrol). |_. cfcontrol |_. F{~B~} |_. Explicaţie |
| $cfcontrol(9, 10) = 9$
| $F{~10~}(9) = 0$
| 9 are o singură cifră, deci 9 o să fie răspunsul final.
|
| $cfcontrol(15, 10) = 6$
| $F{~10~}(15) = 1$
| $15$ are mai cel puţin două cifre, deci $x$ va deveni $1 + 5 = 6$ care are o singură cifră, deci $6$ va fi cifra de control.
|
| $cfcontrol(189, 10) = 9$
| $F{~10~}(189) = 2$
| $189$ are cel puţin două cifre, deci $x$ va deveni $1 + 8 + 9 = 18$. $18$ are cel puţin două cifre, deci $x$ va deveni în continuare $1 + 8 = 9$, deci $9$ va fi cifra de control.
|
| $cfcontrol(76, 7) = 4$
| $F{~7~}(76) = 2$
| *Argumentele din funcţie sunt date în acest exemplu ca numere în baza $10$. În acest caz, ele trebuie văzute ca numere în baza $7$.*
$76$ în baza $7$ va fi $136{~(7)~}$. Acesta are cel puţin două cifre, deci $x$ va deveni $1 + 3 + 6 = 10{~(10)~} = 13{~(7)~}$. $13{~(7)~}$ are în continuare cel puţin două cifre, deci $x$ va deveni $1 + 3 = 4{~(10)~} = 4{~(7)~}$, deci cifra de control va fi $4$.
|
h2. Cerinţă
Se dau $N, B şi M$. Să se calculeze $G{~B~}(N) modulo M$.
h2. Date de intrare
Fişierul de intrare $voodoo.in$ ...
Fişierul de intrare $voodoo.in$ se vor afla pe o singură linie 3 numere separate prin câte un singur spaţiu $N$, $B$ şi $M$ cu semnificaţia din enunţ.
h2. Date de ieşire
În fişierul de ieşire $voodoo.out$ ...
În fişierul de ieşire $voodoo.out$ se va afla valoarea lui $G{~B~}(N) modulo M$. *Răspunsul se va afişa în baza $10$*.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $0 ≤ N ≤ 10^18^$
* $2 ≤ B ≤ 10^18^$
* $B$ *nu* va fi de forma $6k + 1$ sau $9k + 1$ oricare ar fi $k$ număr întreg
* $1 ≤ M ≤ 3^12^$
* $M$ este de forma $3^k^$ unde $k$ este un număr întreg
* Pentru teste în valoare $20$ de puncte, $G{~B~}(N) ≤ 10^18^$
* Pentru alte teste în valoare $50$ de puncte, $N ≤ 250.000$
* Haos.
h2. Exemplu
table(example). |_. voodoo.in |_. voodoo.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| %{color:red}*3 10 531441*%
| %{color:red}*199*%
|
| 3 9 27
| 26
|
| 250000 5007329433060514 531441
| 425803
|
| 1000000000000000000 5007329433060514 531441
| 384844
|
h3. Explicaţie
...
%{color:red}Primul exemplu nu respectă restricţiile din problemă ({$10$} este de forma $9 * 1 + 1$). Acesta a fost pus doar pentru a clarifica enunţul.%
Suma cifrelor lui $199$ este $1 + 9 + 9 = 19$. Suma cifrelor lui $19$ este $1 + 9 = 10$. Suma cifrelor lui $10$ este $1 + 0 = 1$. Am calculat suma cifrelor de $3$ ori, deci $F{~10~}(199) = 3$. Acesta este cel mai mic număr pentru care se obţine rezultatul respectiv.
În al doilea exemplu, răspunsul este $161{~(10)~} = 188{~(9)~}$. Suma cifrelor lui $188{~(9)~}$ este $1 + 8 + 8 = 17 = 18{~(9)~}$. Suma cifrelor lui $18{~(9)~}$ este $1 + 8 = 9 = 10{~(9)~}$. Suma cifrelor lui $10{~9~}$ este $1 + 0 = 1$. Am calculat suma cifrelor de $3$ ori, deci $F{~9~}(161{~(10)~}) = 3$. Acesta este cel mai mic număr pentru care se obţine rezultatul respectiv. $161 modulo 27$ va fi $26$.
Ultimele două exemple sunt prea haos pentru a avea o explicaţie.
== include(page="template/taskfooter" task_id="voodoo") ==
