Pracsiu Dan (dnprx) Tocmai ai primit un șir v de K numere naturale nenule distincte. Plecând de la acest șir, te-ai gândit să construiești un șir w de N numere naturale distincte, astfel încât un număr x este în șirul w dacă și numai dacă exista inițial în șirul v sau se pot alege cel puțin două numere din șirul v astfel încât x este cel mai mare divizor comun al acelor numere. De exemplu, dacă v = {4, 6, 7} atunci w = {1, 2, 4, 6, 7}.
Uimit de proprietățile matematice frumoase ale noului șir w, ai uitat din păcate șirul original v de la care ai pornit.
Cerința
Dându-se șirul w, să se găsească un șir posibil inițial v având un număr minim de elemente.
Date de intrare
Fișierul de intrare comun.in conține pe prima linie un număr natural N. Pe cea de-a doua linie se află N numere naturale nenule distincte, în ordine strict crescătoare, reprezentând șirul w.
Date de ieșire
Fișierul de ieșire comun.out va conține pe prima linie numărul minim K de elemente ale șirului v. Pe cea de-a doua linie se vor afla K numere naturale distincte, în ordine strict crescătoare, reprezentând șirul propriu-zis.
Restricții și precizări
- Toate valorile din fișierul de intrare sunt numere naturale nenule mai mici sau egale cu
100.000. - Pentru teste în valoare de
15puncte, toate valorile din fișierul de intrare sunt mai mici sau egale cu20. - Pentru teste în valoare de
50de puncte, toate valorile din fișierul de intrare sunt mai mici sau egale cu2000. - Se garantează că există măcar o soluție.
- Dacă există mai multe șiruri inițiale cu număr minim de elemente, oricare este acceptat.
Exemplul 1:
comun.in
5 1 2 4 6 7
comun.out
3 4 6 7
Explicație
1 = cmmdc(6, 7) = cmmdc(4, 6, 7). 2 = cmmdc(4, 6). Se poate demonstra că orice alt șir cu proprietatea cerută are măcar 3 elemente.
Exemplul 2:
comun.in
4 2 4 8 16
comun.out
4 2 4 8 16
Explicație
Nu există niciun șir de mai puțin de 4 elemente cu proprietatea cerută.