Iacob Tudor (IacobTudor) Cerința
Se dă un vector A de N elemente. Trebuie să calculați suma celui mai mare divizor comun din toate secvențele vectorului . Mai formal , notând cu F(st , dr) = cmmdc(A[st] , A[st+1] ... A[dr]) 1 <= st <= dr <= N , trebuie să calculați suma tuturor F(st , dr) posibile.
Date de intrare
Fișierul de intrare gcd2.in conține pe prima linie un număr N care reprezintă numărul de elemente din vector , iar pe a doua linie N numere separate prin spațiu reprezentând elementele vectorului A.
Date de ieșire
Fișierul de ieșire gcd2.out conține pe prima linie un număr ans reprezentând suma cerută.
Restricții și precizări
- Numerele sunt naturale , din intervalul
[ 0 , 1.000.000.000 ],NUneapărat distincte. - Se garantează că răspunsul se poate reprezenta pe
64 biti. - Pentru teste in valoare de
20 de puncte , N ≤ 1.000. - Pentru restul testelor ,
N ≤ 100.000.
Exemplu:
gcd2.in
3 1 2 3
gcd2.out
9
gcd2.in
4 5 8 9 3
gcd2.out
33
Explicație
În primul exemplu trebuie calculată suma
F(1 , 1) + F(1 , 2) + F(1 , 3) + F(2 , 2) + F(2 , 3) + F(3 , 3) = 1 + 1 + 1 + 2 + 1 + 3 = 9.