| Fişierul intrare/ieşire: | voodoo.in, voodoo.out | Sursă | Summer Challenge 2020 |
| Autor | Alexandru Petrescu, Tinca Matei | Adăugată de |  Tinca Matei •TincaMatei |
| Timp execuţie pe test | 1 sec | Limită de memorie | 262144 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Voodoo
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:
// 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 FB şi GB.
FB(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 (*)).
GB(n) = x unde x este cel mai mic număr natural nenul în care FB(x) = n.
În următorul tabel sunt prezentate mai multe exemple de calcul al cifrei de control şi al funcţiei FB.
| cfcontrol | FB | Explicaţie |
|---|---|---|
| cfcontrol(9, 10) = 9 | F10(9) = 0 | 9 are o singură cifră, deci 9 o să fie răspunsul final. |
| cfcontrol(15, 10) = 6 | F10(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 | F10(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 | F7(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. |
Cerinţă
Se dau N, B şi M. Să se calculeze GB(N) modulo M.
Date de intrare
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ţ.
Date de ieşire
În fişierul de ieşire voodoo.out se va afla valoarea lui GB(N) modulo M. Răspunsul se va afişa în baza 10.
Restricţii
- 0 ≤ N ≤ 1018
- 2 ≤ B ≤ 1018
- B nu va fi de forma 6k + 1 sau 9k + 1 oricare ar fi k număr întreg
- 1 ≤ M ≤ 312
- M este de forma 3k unde k este un număr întreg
- Pentru teste în valoare 20 de puncte, GB(N) ≤ 1018
- Pentru alte teste în valoare 50 de puncte, N ≤ 250.000
- Haos.
Exemplu
| voodoo.in | voodoo.out |
|---|---|
| 3 10 531441 | 199 |
| 3 9 27 | 26 |
| 250000 5007329433060514 531441 | 425803 |
| 1000000000000000000 5007329433060514 531441 | 384844 |
Explicaţie
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 F10(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 109 este 1 + 0 = 1. Am calculat suma cifrelor de 3 ori, deci F9(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.
