Maricica

Time limit: 0.06s Memory limit: 64MB Input: maricica.in Output: maricica.out

„Iarăși ți-e gândul la Maricica?”

Maricica este o fată silitoare și extrem de frumoasă, însă, în ciuda efortului pe care aceasta îl depune la matematică, nu reușește să ia o notă bună. De curând profesorul de matematică de la clasă le-a predat un capitol nou, intitulat divizibilitate, mai precis, cel mai mic divizor comun al unor numere date, anterior predându-le suma numerelor și îi promite că poate da un test din ambele capitole pentru a-și schimba nota, dar aceasta este deja supraaglomerată cu învățatul la celelalte materii, spre exemplu română, așa că te roagă să o ajuți în rezolvarea testului. Dacă o ajuți aceasta te va răsplăti cu o sută de puncte.

Cerință

Testul are două exerciții:

  1. Dându-se NN și NN numere naturale, se cere găsirea celui mai mare divizor comun al celor NN numere date.
  2. Dându-se NN, QQ, apoi NN numere naturale a1,a2,a3,,aNa_1, a_2, a_3, \dots, a_N, și QQ întrebări de forma [l,r][l, r] unde 1lrN1 \le l \le r \le N, se cere găsirea suma numerelor ala_l, al+1a_{l+1}, al+2a_{l+2}, \dots, ara_r pentru fiecare întrebare.

Date de intrare

Pe prima linie a fișierul de intrare se va afla CC reprezentând numărul exercițiului.

Dacă C=1C = 1 atunci pe a doua linie se va afla un număr NN și pe cea de-a treia linie se vor afla NN numere naturale.

În cazul în care C=2C = 2 atunci pe a doua linie se va afla un număr NN, pe cea de-a treia linie se vor afla NN numere naturale urmat pe rândul următor de QQ ce simbolizează numărul de întrebări urmat de încă QQ rânduri de forma [l,r][l,r] unde 1lrN1 \le l \le r \le N.

Date de ieșire

Dacă C=1C = 1 atunci pe prima linie a fișierului de ieșire se va afla un singur număr, cel mai mare divizor comun al celor NN numere date, iar dacă C=2C = 2 atunci se vor afișa, pe rânduri diferite, răspunsul la cele QQ întrebări.

Restricții și precizări

  • 1N100 0001 \le N \le 100\ 000
  • 0ai1090 \le a_i \le 10^9
  • 1Q10 0001 \le Q \le 10\ 000
  • Prima cerință valorează 3030 de puncte.
  • A doua cerință valorează 7070 de puncte.
  • Pentru teste în valoare de 55 puncte, 0ai1050 \le a_i \le 10^5 și C=1C = 1.
  • Pentru teste în valoare de 2020 de puncte, 1N1 0001 \le N \le 1\ 000 și C=2C = 2.
  • Pentru teste în valoare de 7070 de puncte, 0ai1050 \le a_i \le 10^5 și C=2C = 2.

Exemplul 1

maricica.in

1
5
2 4 10 6 8

maricica.out

2

Exemplul 2

maricica.in

2
5
2 4 10 6 8
3
2 4
1 5
3 5

maricica.out

20
30
24

Log in or sign up to be able to send submissions!