Fişierul intrare/ieşire:deletegcd.in, deletegcd.outSursăJunior Challenge 2019
AutorBogdan PopAdăugată deJuniorChallenge2019Junior Challenge 2019 •JuniorChallenge2019
Timp execuţie pe test1.25 secLimită de memorie255000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Deletegcd

Un şir se numeşte şmecher dacă cel mai mare divizor comun al tuturor elementelor lui este diferit de 1. Un şir se numeşte aproape-şmecher dacă prin ştergerea unui singur element al său acesta devine şmecher.
Se dă un şir de numere naturale A de lungime n şi q întrebări. La o întrebare, se dau 2 indici l şi r şi se cere să determinaţi dacă subsecvenţa de la l la r a şirului A este un şir aproape-şmecher. În particular, un şir care este şmecher este considerat şi aproape-şmecher.

Date de intrare

Fişierul deletegcd.in conţine q+2 linii.
Pe prima linie apar n şi q.
Pe următoarea linie apar n numere, reprezentând elementele şirului A .
Pe urmatoarele q linii apar câte 2 numere, reprezentând parametrii l şi r pentru cele q query-uri.

Date de ieşire

În fişierul deletegcd.out veţi afişa un şir ce conţine caracterele 0 şi 1, fără spaţii.
Pe pozitia i din şir, veţi afişa 1 dacă secvenţa dată la întrebarea i este aproape-şmecheră, respectiv 0 altfel.

Restricţii

  • 1 ≤ N ≤ 106
  • 1 ≤ Q ≤ 106
  • 1 ≤ l < r ≤ N
  • 1 ≤ A[i] ≤ 106
  • Toate secvenţele din întrebări au lungime cel puţin 3.
  • Atenţie!Testele sunt grupate
  • Pentru 15 puncte, 1 ≤ N, Q, A[i] ≤ 102 (grupa testelor 1-3)
  • Pentru alte 20 de puncte 1 ≤ N, Q, A[i] ≤ 103 (grupa testelor 4-7)
  • Pentru alte 40 de puncte 1 ≤ N, Q, A[i] ≤ 2*105 (grupa testelor 8-15)
  • Pentru restul de 25 de puncte, se aplică restricţiile iniţiale (grupa testelor 16-20)
  • ATENŢIE! Se recomandă parsarea fişierului deletegcd.in. Puteţi folosi codul oferit de noi pe siteul in (atât pentru utilizatorii de C++ şi sintaxă similară cu fstream, cât şi pentru iubitorii de C pur)
  • De asemenea, se recomandă să afişaţi ieşirea ca un şir de caractere (nu câte un caracter).

Exemplu

deletegcd.indeletegcd.out
5 3
1 2 3 4 5
1 3
2 4
3 5
010
10 3
95 97 62 15 47 85 26 80 44 18
1 10
4 6
6 9
011
10 36
111174 6 555870 2 30 555870 21 277935 185290 26470
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
2 4
2 5
2 6
2 7
2 8
2 9
2 10
3 5
3 6
3 7
3 8
3 9
3 10
4 6
4 7
4 8
4 9
4 10
5 7
5 8
5 9
5 10
6 8
6 9
6 10
7 9
7 10
8 10
111111001111100111100111001111111111
10 36
1 35 26470 14 5 185290 2 30 10 111174
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
2 4
2 5
2 6
2 7
2 8
2 9
2 10
3 5
3 6
3 7
3 8
3 9
3 10
4 6
4 7
4 8
4 9
4 10
5 7
5 8
5 9
5 10
6 8
6 9
6 10
7 9
7 10
8 10
100000001110000111111111111111111111
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?