Fișierul intrare/ieșire	bas.in, bas.out	Sursă	Olimpiada pe școală 2019
Autor	Andrei Coman	Adăugată de	Andrei Coman • andreicoman
Timp de execuție pe test	0.75 sec	Limită de memorie	131072 KB
Scorul tău	N/A	Dificultate	3

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Bravo, ai şir! (Clasa a 6-a)

Vești bune pentru toți pasionații de șiruri din România: tocmai a început cel de-al șaselea sezon al celui mai prestigios concurs de informatică din întreaga lume, “Bravo, ai șir!”. După cum bine știți, la fel ca la orice competiție respectabilă, juriul este format din M membri cu preferințe foarte stricte, care apreciază doar concurenții “fierți” pe șiruri.

Fiecare concurent trebuie sa prezinte un șir de N numere naturale, asupra căruia poate efectua următoarea operație:

• Alege un element al șirului și îl împarte la un divizor prim al său.

Concurentul poate efectua oricât de multe “operații” asupra șirului, cât timp acestea sunt valide (împărțitorul divide deîmpărțitul). Concursul constă în următoarele probe:

• Proba 1: fiecare membru al juriului adresează următoarea întrebare: “se poate ca, aplicând operații repetate, cel mai mare divizor comun al elementelor șirului să devină X?”

• Proba 2: fiecare membru al juriului adresează următoarea întrebare: “știind că prin aplicarea repetată a unor operații asupra șirului, cel mai mare divizor comun al elementelor poate deveni X, care este numărul minim de operații care trebuie efectuate?”

Atenție! La începutul fiecărei întrebări, modificările precedente nu se păstrează! Știind șirul pe care Alexandru, concurentul vostru preferat, l-a pregătit și proba la care acesta participă, precum și scenariile propuse de juriu, ajutați-l să răspundă corect la toate întrebările. Altfel, el va fi propus pentru eliminare și își va pierde încrederea în sine.

Date de intrare

Pe prima linie a fișierului de intrare bas.in se află 3 numere naturale, P, M și N, reprezentând proba, numărul de jurați, respectiv lungimea șirului prezentat. Pe a doua linie se află N numere naturale, reprezentând elementele șirului. Pe următoarele M linii se va găsi câte un număr X, reprezentând întrebările adresate de fiecare jurat.

Date de ieșire

Pentru prima probă (P = 1), în fișierul de ieșire bas.out se vor găsi M linii cu câte o valoare de 0 sau 1 (1 dacă se poate obține cmmdc-ul dat, altfel 0).

Pentru a doua probă (P = 2), afișați M linii cu câte un număr natural, reprezentând numărul minim de operații care trebuie efectuate asupra șirului pentru a obține cmmmdc-ul dat.

Restricții

• 1 ≤ N ≤ 100.000
• Toate elementele șirului, precum și numerele date de juriu, sunt cuprinse între 1 și 1.000.000.000
• Subtask 1: P = 1 (20 de puncte)
• Subtask 2: P = 2, M = 1 (15 puncte)
• Subtask 2: P = 2, M ≤ 1.000 (50 de puncte)
• Subtask 3: P = 2, M ≤ 10.000 (10 puncte)
• Subtask 4: P = 2, M ≤ 100.000 (5 puncte)
• 1 nu este număr prim
• Atentie! Juriul nu face compromisuri! Veți primi punctajul pe un test doar dacă toate răspunsurile sunt corecte.

Exemplu

Explicație

În primul exemplu:

• cmmdc-ul 1 se obține prin împărțirea lui 60 la 2, la 2 și apoi la 3
• cmmdc-ul 5 nu se poate obține
• cmmdc-ul 12 se obține cu 0 operații
• cmmdc-ul 6 se obține prin împărțirea lui 36 la 2
• cmmdc-ul 18 nu se poate obține

În al doilea exemplu:

• cmmdc-ul 1 se obține prin împărțirea lui 36 la 2 de doua ori, apoi prin împărțirea lui 24 la 3
• cmmdc-ul 4 se obtine prin împărțirea lui 24 la 3
• cmmdc-ul 12 se obține cu 0 operații
• cmmdc-ul 6 se obține prin împărțirea lui 36 la 2
• cmmdc-ul 4 se obține prin împărțirea lui 24 la 3.