Fişierul intrare/ieşire:primesato.in, primesato.outSursăAGM 2019, runda finala
AutorTamio-Vesa NakajimaAdăugată detamionvTamio Vesa Nakajima tamionv
Timp execuţie pe test3 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Primesato

Primesato este complet obsedata de numerele prime, si astfel a creat urmatoarea problema: se dau trei numere N, M si K. Cate secvente S de N numere intregi intre 1 si K exista astfel incat toate subsecventele de lungime prima a lui S au suma para? Raspunsul se cere modulo M.

Date de intrare

Fişierul de intrare primesato.in va contine, pe primul rand, numarul T de teste din fisier
Pe urmatoarele T randuri vor aparea descrierile celor T teste, adica numerele N, M, K, cu semnificatia din enunt.

Date de ieşire

În fişierul de ieşire primesato.out vor aparea cate T randuri, fiecare cu raspunsul pentru cate un test, in ordine.

Restricţii

  • 1 ≤ T ≤ 100.000
  • 1 ≤ N, K ≤ 1018
  • 1 ≤ M ≤ 109

Exemplu

primesato.inprimesato.out
3
3 100 2
23 23 23
14343 23512 43646
1
11
6111
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?