Editing 1735 - divquery (section)

==Explicație cod==
Acest cod este o implementare a unei soluții pentru problema "DivQuery", care se ocupă cu determinarea celui mai mare divizor comun dintr-un interval dat dintr-un șir de numere.

Funcția "cmmdc(a, b)" calculează cel mai mare divizor comun dintre două numere folosind algoritmul Euclid.

Funcția "read_input(filename)" citește datele de intrare dintr-un fișier și returnează numărul de elemente din șir (n), lista cu elementele (a) și o listă cu perechi de numere (queries), reprezentând intervalele pentru care trebuie calculat cel mai mare divizor comun.

Funcția "compute_logs(n)" calculează logaritmul în baza 2 pentru numerele de la 2 la n și returnează o listă cu valorile obținute. Aceste valori sunt utilizate pentru a determina numărul de niveluri din tabelul rar.

Funcția "compute_sparse_table(a)" construiește un tabel rar (sparse table) pentru șirul de numere dat (a). Tabelul este reprezentat ca o matrice (st) cu (logs[n]+1) niveluri și n coloane. Primul nivel al matricei conține elementele din șir, iar fiecare nivel următor se construiește pe baza nivelului precedent. Matricea este construită astfel încât pentru orice subinterval din șir se poate calcula cel mai mare divizor comun folosind două valori din tabelul rar.

Funcția "process_queries(a, queries, st, logs)" calculează cel mai mare divizor comun pentru fiecare interval din lista de intervale (queries) folosind tabela rară și returnează o listă cu rezultatele obținute.

Funcția "write_output(filename, results)" scrie rezultatele într-un fișier de ieșire.

Funcția "validate_input(n, a, q)" verifică dacă datele de intrare sunt valide, adică numărul de elemente din șir să fie între 1 și 100000, elementele din șir să fie între 1 și 100000, iar intervalele să fie între 1 și 1000000.

Blocul "if name == 'main':" este partea principală din cod care apelează celelalte funcții pentru a rezolva problema și afișează un mesaj de eroare în cazul în care datele de intrare nu sunt valide.