Fişierul intrare/ieşire: | heavytask.in, heavytask.out | Sursă | ONIS 2014, Runda 2 |
Autor | Dragos Oprica | Adăugată de | |
Timp execuţie pe test | 0.2 sec | Limită de memorie | 12288 kbytes |
Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Heavytask
Petrica are o noua problema grea pe care vrea sa o rezolve. El are un sir A de lungime N format din numere naturale strict pozitive si vrea sa obtina un sir B de numere naturale strict pozitive de lungime N cu urmatoarele proprietati: B[i] divide pe A[i] oricare ar fi 1 ≤ i ≤ N si cel mai mic multiplu comun al numerelor din sirul A trebuie sa fie egal cu cel mai mic multiplu comun al numerelor din sirul B. In cazul in care exista mai multe siruri B care respecta cele doua proprietati, Petrica vrea sa il obtina pe cel mai mic din punct de vedere lexicografic.
Date de intrare
Fişierul de intrare heavytask.in contine pe prima linie un numar natural T reprezentand numarul de teste. Prima linie a unui test contine un numar natural N care reprezinta lungimea sirului. Pe urmatoarea linie a unui test se vor afla N numere separate printr-un spatiu reprezentand sirul A.
Date de ieşire
În fişierul de ieşire heavytask.out veti afisa T linii, fiecare linie continand N numere separate printr-un spatiu, reprezentand sirul B pentru testul corespunzator din fisierul de intrare.
Restricţii
- T = 5
- 1 ≤ N ≤ 300
- 1 ≤ A[i] ≤ 1018
Exemplu
heavytask.in | heavytask.out |
---|---|
2 2 1 2 5 210 2 3 5 7 | 1 2 1 2 3 5 7 |
Explicaţie
Pentru primul test singura solutie posibila este sirul 1, 2. Pentru cel de-al doilea test exista mai multe solutii posibile, iar cea mai mica lexicografica este sirul 1, 2, 3, 5, 7.