Fişierul intrare/ieşire:gcd.in, gcd.outSursăHappy Birthday Infoarena 2014
AutorPaul-Dan BaltescuAdăugată deeudanipEugenie Daniel Posdarascu eudanip
Timp execuţie pe test0.6 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Gcd

Se dau 2 numere naturale N si M. Sa se determine cel mai mare divizor comun dintre N_secund = 2N - 1 si M_secund = 2M - 1. Raspunsul trebuie afisat modulo P.

Date de intrare

Fişierul de intrare gcd.in va contine pe prima linie un numar natural T, reprezentand numarul de teste. Pe urmatoarele T linii vor fi cate 3 numere naturale N, M si P.

Date de ieşire

Fişierul de ieşire gcd.out va contine T linii, pe linia i aflandu-se raspunsul pentru testul i.

Restricţii

  • 1 ≤ N,M,P ≤ 1.000.000.000
  • 1 ≤ T ≤ 100.000

Exemplu

gcd.ingcd.out
2
2 3 100
2 4 100
1
3

Explicaţie

Cel mai mare divizor comun dintre 3 si 7 este 1 iar cel mai mare divizor comun dintre 3 si 15 este 3.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?