$$ \newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor} \newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil} \newcommand{\mod}{\,\mathrm{mod}\,} \newcommand{\div}{\,\mathrm{div}\,} \newcommand{\metar}{\,\mathrm{m}} \newcommand{\cm}{\,\mathrm{cm}} \newcommand{\dm}{\,\mathrm{dm}} \newcommand{\litar}{\,\mathrm{l}} \newcommand{\km}{\,\mathrm{km}} \newcommand{\s}{\,\mathrm{s}} \newcommand{\h}{\,\mathrm{h}} \newcommand{\minut}{\,\mathrm{min}} \newcommand{\kmh}{\,\mathrm{\frac{km}{h}}} \newcommand{\ms}{\,\mathrm{\frac{m}{s}}} \newcommand{\mss}{\,\mathrm{\frac{m}{s^2}}} \newcommand{\mmin}{\,\mathrm{\frac{m}{min}}} \newcommand{\smin}{\,\mathrm{\frac{s}{min}}} $$

Prijavi problem


Obeleži sve kategorije koje odgovaraju problemu

Još detalja - opišite nam problem


Uspešno ste prijavili problem!
Status problema i sve dodatne informacije možete pratiti klikom na link.
Nažalost nismo trenutno u mogućnosti da obradimo vaš zahtev.
Molimo vas da pokušate kasnije.

Uvod u algoritme

Pitaj na Algori

Najveci NZD

Autor zadatka
Saradnici
Autor rešenja zadatka
Izvor zadatka
vreme memorija ulaz izlaz
10 s 128 Mb standardni ulaz standardni izlaz

Dat je niz prirodnih brojeva a od n elemenata. U jednom potezu dozvoljeno je odabrati proizvoljna dva susedna broja u nizu i zameniti ih njihovim zbirom. Na primer, ukoliko smo odabrali brojeve ai i ai + 1, niz (a1, a2, ..., ai, ai + 1, ... an) postaje (a1, a2, ..., ai + ai + 1, ... an). Ovo zatim možemo ponavljati na novodobijenim nizovima (primetimo da se broj elemenata niza svaki put smanjuje za 1).

Primeniti određeni broj poteza nad početnim nizom, tako da na kraju dobijemo tačno k brojeva čiji je najveći zajednički delilac najveći moguć.

U prvom redu standardnog ulaza nalaze se 2 prirodna broja n i k koji predstavljaju, redom, broj elemenata u početnom nizu i broj elemenata koji treba ostati na kraju. Sledeći red sadrži n prirodnih brojeva ai (razdvojenih razmakom) koji predstavljaju početni niz. 

U prvom redu standardnog ispisati maksimalni moguć najveći zajednički delilac preostalih brojeva. U drugom redu ispisati k prirodnih brojeva razdvojenih razmakom - izgled niza nakon svih poteza, čiji je najveći zajednički delilac maksimalan. Ukoliko ima više rešenja, štampati bilo koje.

1 ≤ k < n ≤ 100.000

1 ≤ ai ≤ 1.000.000

Suma svih elemenata niza a nije veća od 1.000.000.

Ulaz Izlaz
6 3
12 7 3 2 15 15
6
12 12 30

Ukoliko izvršimo poteze (12, 7, 3, 2, 15, 15) → (12, 10, 2, 15, 15) → (12, 10, 2, 30) → (12, 12, 30) dobijamo brojeve 12, 12 i 30 čiji je najveći zajednički delilac jednak 6. Nije moguće dobiti 3 broja sa većim najvećim zajedničkim deliocem.

Morate biti ulogovani kako biste poslali zadatak na evaluaciju.