Fişierul intrare/ieşire:dlog.in, dlog.outSursăInfoarena Cup 2012
AutorCosmin GheorgheAdăugată defreak93Adrian Budau freak93
Timp execuţie pe test0.5 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Dlog

Aceasta problema este sponsorizata de IXIA

Se da un numar natural prim P. Definim ZP ca fiind multimea tuturor resturilor posibile modulo P, adica {0, 1, 2, ... P - 1}. Toate operatiile asupra numerelor din ZP se realizeaza modulo P. De exemplu, in Z5, 3 * 3 = 4 (9 mod 5).

Spunem despre un numar natural G, din multimea {1, 2, ... P - 1} ca este generator al lui ZP cu inmultirea daca, ridicandu-l la anumite puteri, putem obtine toate numerele din ZP \ {0}. De exemplu, 2 este generator al lui Z5, deoarece: 21 = 2, 22 = 4, 23 = 3, 24 = 1 (toate operatiile sunt realizate modulo 5). Pe de alta parte, 2 nu este un generator al lui Z7, deoarece nu se poate obtine numarul 5 prin operatia descrisa.

Dandu-se un numar prim P, un numar G, generator al lui ZP, si un numar Y apartinand multimii {1, 2, 3, ... P - 1}, sa se gaseasca X minim, cu proprietatea ca GX = Y (mod P).

Date de intrare

Fişierul de intrare dlog.in va contine pe prima linie T, numarul de query-uri din fisierul de intrare. Pe fiecare dintre urmatoarele T linii se va gasi cate un query, in formatul P, G, Y, cu semnificatia de mai sus.

Date de ieşire

Fişierul de ieşire dlog.out va contine raspunsurile la cele T query-uri, pe linii separate.

Restricţii

  • 1 ≤ T ≤ 1.000
  • 2 ≤ P ≤ 2.000.000
  • 1 ≤ G, Y < P
  • Pentru fiecare dintre cele T teste, raspunsul trebuie sa se regaseasca in intevalul [0 .. P - 1]

Exemplu

dlog.indlog.out
3
3 2 1
5 3 2
7 3 4
0
3
4

Explicaţie

2^0 MOD 3 = 1 MOD 3 = 1
3^3 MOD 5 = 27 MOD 5 = 2
3^4 MOD 7 = 81 MOD 7 = 4

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content