E. Хуваагч мод

хугацааны хязгаарлалт 0.5 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Хуваагч мод гэдэг нь дараах нөхцлүүдийг хангасан үндэстэй мод юм. Үүнд:

  • Модны орой бүрд нь эерэг бүхэл тоо байна.
  • Модны навчин дээр бичигдсэн тоонууд нь анхны тоонууд байна.
  • Аль ч дотор оройн (навч биш) хувьд түүн дээрх утга нь хүүхэд оройнуудад дээр бичигдсэн тоонуудын үржвэртэй тэнцүү байна.

Манаод $n$ ширхэг ялгаатай бүхэл $a_{1}, a_{2}, ..., a_{n}$ тоонууд байгаа. Тэр эдгээр тоонуудыг бүгдийг агуулсан хуваагч модыг байгуулах гэж оролдож байна. Өөрөөр хэлбэл $a_{i}$ бүр нь модны аль нэг оройд байх ёстой. Манао авсаархан загварт дуртай ч түүний байгуулах мод нь хэтэрхий том болох гээд байв.

Манаод боломжит хамгийн цөөн оройтой хуваагч модыг байгуулахад нь тусална уу.

Оролт

Эхний мөрөнд нэг бүхэл $n$ ($1 ≤ n ≤ 8$) тоо агуулагдана. Хоёр дахь мөрөнд зайгаар тусгаарлагдсан ялгаатай $n$ ширхэг бүхэл $a_{i}$ ($2 ≤ a_{i} ≤ 10^{12}$) тоонууд агуулагдана.

Гаралт

Нэг бүхэл тоо хэвлэнэ. Энэ бол $a_{i}$ тоонуудыг агуулсан хамгийн жижиг хуваагч модны оройнуудын тоо.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
2
6 10
Гаралт
7
Оролт
4
6 72 8 4
Гаралт
12
Оролт
1
7
Гаралт
1

Тэмдэглэл

Жишээ 1. Хамгийн бага хуваагч мод нь ийм байдалтай харагдана:

Жишээ 2. Энэ тохиолдолд та дараах хуваагч модыг байгуулж болно:

Жишээ 3. Мод нь нэг оройноос бүрдэж болно гэдгийг анхаараарай.

Сэтгэгдлүүдийг ачааллаж байна...