Matematicianul
maghiar Paul Erdos (1913–1996) a demonstrat ca din orice multime de p*q+1
numere naturale, putem selecta p+1
numere care se divid succesiv (x1|x2|...|xp|xp+1)
sau putem selecta q+1 numere,
astfel incat oricare doua dintre numere nu se divid ele.
Cerinta
Date fiind p*q+1
numere naturale distincte, sa se determine o submultime de p+1
numere care se divid succesiv sau o submultime de q+1
numere care nu se divid intre ele.
Date de intrare
Fisierul de intrare erdos.in
contine pe prima linie numerele naturale p
si q separate printr-un singur
spatiu. Pe cea de a doua linie se afla p*q+1
numere naturale distincte separate prin cate un spatiu. Numerele sunt date in
ordine crescatoare.
Date de iesire
Fisierul de iesire erdos.out
va contine pe prima linie numarul natural p
sau numarul natural q. Daca pe
prima linie este scris numarul natural p,
atunci pe cea de a doua linie sunt scrise p+1
numere naturale dintre cele citite, care au proprietatea ca primul numar il
divide pe al doilea, al doilea il divide pe al treilea, s.a.m.d. Daca pe prima
linie este scris numarul natural q,
atunci pe cea de a doua linie vor fi scrise q+1
numere naturale cu proprietatea ca oricare doua numere dintre cele q+1
afisate nu se divid intre ele. Numerele afisate pe aceeasi linie vor fi separate
prin spatiu si vor fi in ordine crescatoare.
Restrictii si precizari
1 <= p, q <= 50
p<>q
Numerele naturale date
au valori < 263
Exemple
erdos.in
erdos.out
Explicatie
3 4
3 5 9 12 14 15 24 33 35 41 51 54 61
4
9 12 15 33 35
Oricare
doua numere din multimea {9 12 15
33 35} nu se divid intre ele.