| Fişierul intrare/ieşire: | cmmdc2.in, cmmdc2.out | Sursă | ONI 2016, clasa a 9-a |
| Autor | Dan Pracsiu, Stelian Ciurea | Adăugată de |  Alexandru Valeanu •AlexandruValeanu |
| Timp execuţie pe test | 0.4 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Cmmdc2
Fie un şir de numere naturale nenule a1, a2, ..., an şi un număr natural k.
Cerinţă
Să se determine un grup de k numere din şir care au proprietatea ca cel mai mare divizor comun al lor este maxim.
Dacă există mai multe astfel de grupuri, se cere acel grup pentru care suma elementelor este maximă.
Date de intrare
Fişierul de intrare cmmdc2.in conţine pe prima linie numerele naturale n şi k separate prin spaţiu. Pe linia a doua se găsesc numerele naturale a1, a2, ..., an separate prin câte un spaţiu.
Date de ieşire
În fişierul de ieşire cmmdc2.out conţine pe prima linie un număr natural reprezentând cel mai mare divizor comun a exact k numere din şir, maxim posibil.
Pe linia a doua, separate prin câte un spaţiu şi ordonate descrescător, se află cele k numere din şir care dau cel mai mare divizor comun maxim.
Restricţii
- 1 ≤ n ≤ 1.000.000
- 1 ≤ k ≤ 100.000
- k ≤ n
- 1 ≤ ai ≤ 1.000.000, pentru 1 ≤ i ≤ n
- Valorile din şir se pot repeta.
Exemplu
| cmmdc2.in | cmmdc2.out | Explicaţie |
|---|---|---|
| 6 3 6 9 8 10 15 3 | 3 15 9 6 | Cel mai mare divizor comun care se poate obţine dintr-un grup de 3 numere este 3, iar cele 3 numere care dau suma maximă, ordonate descrescător, sunt 15, 9 şi 6. |
