Revizia anterioară Revizia următoare
| 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
Gojo are in faţa lui un şir de N păpuşi cu diverse înălţimi distincte. Gojo vinde căte o subsecvenţă continuă de păpuşi odată. O subsecvenţă continuă de lungime L cu înălţimea 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. Gojo 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 păpuşi, şi pe al doilea rând înălţimile păpuşilor.
Date de ieşire
În fişierul de ieşire gcdseq.out se va afişa suma cerută, modulo 109+7.
Restricţii
- 1 ≤ N ≤ 100 000.
- 1 ≤ înălţimea unei păpuşi ≤ 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.
