Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | elhc.in, elhc.out | Sursă | ONSEPI 2021, clasa a 9-a |
| Autor | Alexandru Petrescu, Stefania Ionescu, Vlad Gavrila | Adăugată de |  Arhire Andrei •Andrei-27 |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 32000 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Elhc
După şase ani de lucru, Charles a terminat de curăţat instalaţiile pentru producerea negrului de fum din Copşa Mică. Pentru a se ţine departe de mesele de Blackjack, el s-a angajat la CERN, unde va lucra la noul accelerator de particule numit Even Larger Hadron Collider (ELHC).
ELHC are forma unui tunel circular cu o circumferinţă de P kilometri, P fiind un număr prim. De-a lungul tunelului sunt plasaţi P senzori numerotaţi de la 0 la P-1, distanţa dintre doi senzori consecutivi fiind de exact 1 kilometru.
Un experiment efectuat în ELHC constă în studierea unei particule de tip G, 1 ≤ G < P. Dacă această particulă este ridicată la nivelul de energie k şi este lansată din dreptul senzorului 0 în direcţia senzorului 1, ea va parcurge exact G^k kilometri prin tunel şi apoi se va dezintegra, declanşând în acel moment senzorul s în dreptul căruia are loc dezintegrarea particulei.
Se consideră că experimentul are date complete dacă, lansând P-1 particule de tip G ridicate la toate nivelurile de energie k de la 1 la P-1, este posibil să declanşăm toţi senzorii s numerotaţi cu valori între 1 şi P-1, adică toţi senzorii din tunel mai puţin senzorul 0.
Dându-se T perechi de numere G şi P, determinaţi dacă experimentul pentru studierea particulei de tip G într-un tunel de circumferinţă P produce date complete.
Date de intrare
Fişierul de intrare elhc.in conţine pe prima linie un număr T, reprezentând numărul de experimente care vor fi efectuate. Pe fiecare din următoarele T linii se află câte două numere G şi P separate printr-un spaţiu, reprezentând efectuarea unui experiment cu o particulă de tip G într-un tunel de circumferinţă P.
Date de ieşire
În fişierul de ieşire elhc.out se va afla o singură linie cu T biţi scrişi unul după altul, adică fără spaţii între ei. Al i-ulea bit este 1 dacă pentru cel de-al i-lea experiment putem obţine date complete, şi 0 în caz contrar.
Restricţii
- 1 ≤ T ≤ 103,
- 1 ≤ G < P < 109,
- P este un număr prim,
- Subtask 1 - 7 puncte - P ≤ 100,
- Subtask 2 - 14 puncte - P ≤ 10^4^^,
- Subtask 3 - 53 de puncte - P ≤ 10^6^^,
- Subtask 4 - 26 de puncte - nu există restricţii suplimentare.
Exemplu
| elhc.in | elhc.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
