Fişierul intrare/ieşire:euclid1.in, euclid1.outSursăRMI 2015
AutorFlorin ChiricaAdăugată debciobanuBogdan Ciobanu bciobanu
Timp execuţie pe test1.25 secLimită de memorie131072 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Euclid1

După ce aţi mâncat la restaurantul lui Deadpool şi aţi scăpat din Matrix, vi se cere acum să vă întoarceţi în lume antică, mai exact la momentul inventării celui mai mare divizor comun.

În minunatul oraş Alexandria domnea un rege vicios. Regatul său era format din N oraşe aşezate în linie dreaptă şi numerotate de la 1 la N, iar fiecare oraş trebuia să plătească taxe (oraşul i trebuie să plătească Vi monezi iniţial).

Din când în când, regele dorea să crească anumite taxe sau să îl întrebe pe Euclid care este cel mai mare număr care divide toate taxele dintr-un interval de oraşe.

Cerinţă

Fiind dat şirul iniţial V, unde Vi reprezintă numărul de monezi pe care oraşul i trebuie să le plătească regelui. Vi se cere să aplicaţi Q operaţii pe acest şir, operaţii care se pot împarţi în două categorii:

  • query(a, b) - vi se cere să îl ajutaţi pe Euclid să calculeze cel mai mare divizor comun al valorilor Va, Va+1, Va+2, ..., Vb
  • update(a, b, k) - regele măreste taxele după cum urmează:
    • Va += k
    • Va+1 += 2 x k
    • Va+2 += 3 x k
    • ...
    • Vb += (b - a + 1) x k

Date de intrare

Fişierul de intrare euclid1.in conţine pe prima linie două numere întregi N şi Q, reprezentând numărul oraşelor, respectiv numărul întrebărilor regelui. A doua linie conţine N numere întregi, şirul V. Următoarele Q linii conţin o operaţie, fiecare descrisă după cum urmează:

  • dacă operaţia este query(a, b), atunci linia va conţine trei numere întregi: 0 a b
  • dacă operaţia este update(a, b, k), atunci linia va conţine patru numere întregi: 1 a b k

Date de ieşire

Fişierul de ieşire euclid1.out trebuie să conţină răspunsul pentru fiecare întrebare de tip query, în ordinea în care acestea sunt date, separând fiecare răspuns prin câte o linie nouă.

Restricţii

  • 1 ≤ N ≤ 100.000
  • 1 ≤ Q ≤ 100.000
  • 1 ≤ a ≤ b ≤ N pentru toate operaţiile.
  • 1 ≤ k ≤ 200.000.000 pentru toate operaţiile de tip update.
  • 1 ≤ Vi ≤ 200.000.000 (∀) 1 ≤ i ≤ N
  • Pentru 20% dintre teste N, Q ≤ 1.000
  • Pentru alte 40% dintre teste N, Q ≤ 70.000

Exemplu

euclid1.ineuclid1.outExplicaţie
8 3
2 8 12 24 66 33 21 7
0 2 4
1 1 4 2
0 2 4
4
2
Pentru prima operaţie: se calculeaza cmmdc(8, 12, 24) = 4
In urma celei de a doua operaţie, şirul devine: (4, 12, 18, 32, 66, 33, 21, 7)
A treia operaţie: cmmdc(12, 18, 32) = 2
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?