| 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 ≤ 104,
- Subtask 3 - 53 de puncte - P ≤ 106,
- Subtask 4 - 26 de puncte - nu există restricţii suplimentare.
Exemplu
| elhc.in | elhc.out |
|---|---|
| 6 2 3 3 5 2 7 3 7 3 11 5 11 | 110100 |
Explicaţie
Fişierul de intrare conţine T=6 experimente.
A doua particulă are tipul 3 şi va fi lansată printr-un tunel de circumferinţă 5, cu 5 senzori numerotaţi de la 0 la 4. Ridicată la nivelurile de energie 1, 2, 3, respectiv 4, şi lansată de fiecare dată din dreptul senzorului 0, particula va călători 3, 9, 27, respectiv 81 de kilometri şi va declanşa senzorii 3, 4, 2, respectiv 1. Aceştia sunt toţi senzorii pe care trebuie să-i declanşăm, prin urmare experimentul produce date valide, deci al doilea bit din şirul afişat este 1.
A treia particulă are tipul 2 şi va fi lansată printr-un tunel de circumferinţă 7. Ridicată la nivelurile de energie 1, 2, 3, 4, 5, respectiv 6, şi lansată de fiecare dată din dreptul senzorului 0, particula va declanşa senzorii 2, 4, 1, 2, 4, respectiv 1. Deoarece nu declanşăm senzorii 3, 5 şi 6, experimentul nu are date complete, deci al treilea bit din şirul afişat este 0.
