Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | rick.in, rick.out | Sursă | InfoOltenia 2018 - Clasa a 10-a |
| Autor | Bogdan Iordache | Adăugată de |  Info-Oltenia 2018 •infooltenia |
| Timp execuţie pe test | 1 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Rick
După succesul avut cu melodia “Get Schwifty!”, Rick a început să considere posibilitatea unei cariere în muzică. De-a lungul călătoriilor sale inter-dimensionale a strâns o colecţie impresionantă de N sunete. Fiecare sunet este descris prin frecvenţa sa, măsurată în BPM (beats per minute).
Rick a inventat un dispozitiv care, având la dispoziţie o mulţime de N sunete, alege aleator o submulţime a acestei mulţimi. Sunetele acestei submulţimi sunt combinate, rezultând o melodie. Calitatea unei melodii este dată de cel mai mare divizor comun al frecvenţelor sunetelor combinate. Rick nu este niciodată mulţumit de melodia obţinută aşa că mereu resetează dispozitivul pentru a obţine alte melodii.
Cerinţă
Rick e mulţumit să găsească suma calităţilor tuturor submulţimilor posibile din mulţimea de N sunete.
Date de intrare
Prima linie a fişierului rick.in va conţine numărul natural N, cu semnificaţia din enunţ.
A doua linie va conţine N numere naturale, reprezentând frecvenţele sunetelor din colecţia lui Rick.
Date de ieşire
În fişierul rick.out afişaţi pe prima linie restul împărţirii sumei cerute la 1.000.000.007.
Restricţii
- 1 ≤ N ≤ 500.000
- 1 ≤ frecvenţele sunetelor ≤ 500.000
- pentru 15% din punctaj 1 ≤ N ≤ 20
- pentru alte 25% din punctaj 1 ≤ N, diferenţa în modul dintre oricare două frecvenţe ≤ 1.000
- pentru alte 35% din punctaj 1 ≤ N, frecvenţele sunetelor ≤ 100.000
- prin probabilitate uniformă înţelegem că orice submulţime are aceeaşi probabilitate să fie extrasă de către dispozitiv
- considerăm că submulţimea vidă are cel mai mare divizor comun 1
Exemplu
| rick.in | rick.out |
|---|---|
| 3 2 6 4 | 21 |
Explicaţie
Avem 8 submulţimi posibile. Calculând cel mai mare divizor comun al elementelor fiecărei submulţimi, obţinem valorile: 1, 2, 6, 4, 2, 2, 2, 2.
