Pagini recente » Diferente pentru utilizator/cadmium_ intre reviziile 28 si 146 | Diferente pentru utilizator/catalin_cristian intre reviziile 3 si 7 | Diferente pentru utilizator/razyelx intre reviziile 46 si 13 | Diferente pentru utilizator/cadmium_ intre reviziile 58 si 57 | Diferente pentru problema/distrugere intre reviziile 8 si 19
Diferente intre titluri:
Diferente intre continut:
Considerăm un şir format din $N$ numere naturale. Definim operaţia _distrugere-X_ astfel:
* se alege un număr natural $X$ care apare în şir;
* se şterg toate numerele din şir care au cel puţin un divizor comun cu $X$ mai mare decât 1.
Operaţia _distrugere-X_ se aplică o singură dată.
Fişierul de ieşire $distrugere.out$ conţine o singură linie pe care este scris numărul maxim de elemente care pot rămâne în şir după aplicarea unei singure operaţii _distrugere-X_.
h2. Restricţii
h2. Restricţii şi precizări
* $2 ≤ N ≤ 200 000$
* $1 ≤ elementele şirului ≤ 1 000 000$
* $... ≤ ... ≤ ...$
|_. # |_. Punctaj |_. Restricţii |
| 1 | 14 | $2 ≤ N ≤ 1 000$ |
| 2 | 36 | $1 001 ≤ N ≤ 50 000$ |
| 3 | 50 | Fără restricţii suplimentare |
h2. Exemplu
table(example). |_. distrugere.in |_. distrugere.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 4
15 2 6 9
| 2
|
h3. Explicaţie
...
Există 4 variante de alegere a valorii $X$:
* $X$ = 15: se elimină 6, 9, 15 şi rămâne 1 element (2).
* $X$ = 2: se elimină 2, 6 şi rămân 2 elemente (9, 15);
* $X$ = 6: se elimină 2, 6, 9, 15 şi rămân 0 elemente;
* $X$ = 9: se elimină 6, 9, 15 şi rămâne 1 element (2);
Numărul maxim de elemente rămase este 2.
== include(page="template/taskfooter" task_id="distrugere") ==
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.
