Fişierul intrare/ieşire:bacterii.in, bacterii.outSursăInfoarena Monthly 2014, Runda 4
AutorAdrian BudauAdăugată deTeodor94Teodor Plop Teodor94
Timp execuţie pe test0.1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Bacterii

Recent, cercetătorii institutului CDC au început să studieze amănunţit procesul de multiplicare al bacteriilor Streptococcus paracetivorus. Aceştia au observat o anomalie şi anume, din N bacterii iniţiale, după un pas de multiplicare, acestea devin N * (N - 3) + N + 2 bacterii. Pentru a preveni o creştere rapidă a acestui tip de bacterii, cercetătorii au nevoie să ştie câte bacterii vor exista după K paşi de multiplicare, modulo M, unde M este număr prim.

Cerinţă

Se dă T, numărul de teste, iar pentru fiecare test 3 numere naturale N, K şi M. Să se spună câte bacterii vor exista după K paşi de multiplicare ştiind că iniţial existau N bacterii. Pentru fiecare test, rezultatul cerut se va afişa modulo M.

Date de intrare

Fişierul de intrare bacterii.in conţine pe prima linie numărul de teste, T. Pe următoarele T linii, pentru fiecare test, se găsesc 3 numere naturale N, K şi M, având semnificaţia din enunţ.

Date de ieşire

În fişierul de ieşire bacterii.out se vor găsi T linie, iar fiecare linie i va conţine un singur număr natural, reprezentând rezultatul dorit pentru testul i.

Restricţii

  • 1 ≤ T ≤ 1.000
  • 1 ≤ N ≤ 109
  • 1 ≤ K ≤ 1018
  • 3 ≤ M ≤ 109
  • M este număr prim!

Exemplu

bacterii.inbacterii.out
1
3 3 97
63

Explicaţie

După primul pas, numărul de bacterii devine 3 * 0 + 3 + 2, şi anume 5.
După al doilea pas, numărul de bacterii devine 5 * 2 + 5 + 2, şi anume 17.
După al treilea pas, numărul de bacterii devine 17 * 14 + 17 + 2, şi anume 257.
257 % 97 = 63.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content