| Fişierul intrare/ieşire: | gcdseq.in, gcdseq.out | Sursă | Algoritmiada 2022, Runda 2 |
| Autor | Tamio-Vesa Nakajima | Adăugată de |  Tamio Vesa Nakajima •tamionv |
| Timp execuţie pe test | 1.5 sec | Limită de memorie | 262144 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Gcdseq
Teognis are in faţa lui un şir de N poezii lirice cu diverse frumuseţi distincte. Teognis vinde căte o subsecvenţă continuă de poezii deodată. O subsecvenţă continuă de lungime L cu frumuseţea maximă egală cu M se vinde cu preţul de G lei, unde G este cel mai mare divizor comun al lui L şi M. Teognis a primit dintr-o dată o grămadă de comenzi, câte una pentru fiecare subsecvenţă continuă posibilă. El se întreabă acum: care e suma preţurilor comenzilor ce le-am primit?
Date de intrare
Fişierul de intrare gcdseq.in conţine pe primul rând pe N, numărul de poezii, şi pe al doilea rând frumuseţile poeziilor.
Date de ieşire
În fişierul de ieşire gcdseq.out se va afişa suma cerută.
Restricţii
- 1 ≤ N ≤ 100 000.
- 1 ≤ frumuseţea unei poezii ≤ 400 000.
- Pentru 10 puncte, N ≤ 100.
- Pentru alte 20 de puncte, N ≤ 1 000.
Exemplu
| gcdseq.in | gcdseq.out |
|---|---|
| 5 1 2 3 4 5 | 26 |
| 10 1 5 3 2 4 6 9 8 7 10 | 107 |
Explicaţie
Pentru primul test, preţul subsecvenţelor de lungime 1 este 1; al subsecvenţelor de lungime 2 sunt gcd(2, 2) = 2, gcd(2, 3) = 1, gcd(2, 4) = 2, gcd(2, 5) = 1; al subsecvenţelor de lungime 3 sunt gcd(3, 3) = 3, gcd(3, 4) = 1, gcd(3, 5) = 1; al subsecvenţelor de lungime 4 sunt gcd(4, 4) = 4, gcd(4, 5) = 1; şi preţul subsecvenţei unice de lungime 5 este gcd(5, 5) = 5. Astfel rezultatul este 5 * 1 + 2 + 1 + 2 + 1 + 3 + 1 + 1 + 4 + 1 + 5 = 26.
