25ος ΠΔΠ B' Φάση Λυκείου
Οι μυστικοί αριθμοί (scidinner)

Στο δείπνο που παρατίθεται κατά τη διάρκεια του φετινού πανελλήνιου συνέδριου πληροφορικής παρευρίσκονται \(N\) επιστήμονες. Φαίνεται όμως πως αυτοί ενδιαφέρονται λιγότερο για το φαγητό και περισσότερο για τις ευκαιρίες πνευματικής τροφής που τους δίνονται. Kι έτσι κάπως προκύπτει το πρόβλημα που πρέπει να λύσετε…

Πρόβλημα

Kάθε ένας από τους \(N\) επιστήμονες που παρευρίσκονται στο δείπνο έχει στο μυαλό του ένα θετικό φυσικό αριθμό, διαφορετικό από τους αριθμούς όλων των συναδέλφων του, τον οποίο κρατάει μυστικό. Ο διοργανωτής του δείπνου θέλει να μοιράσει τους επιστήμονες σε ομάδες, αποτελούμενες από ένα ή περισσότερα μέλη, ούτως ώστε σε καμία ομάδα να μην υπάρχουν δύο επιστήμονες που ο μυστικός αριθμός του ενός να διαιρεί ακριβώς το μυστικό αριθμό του άλλου. Mη γνωρίζοντας τους μυστικούς αριθμούς των επιστημόνων, θέλει τη βοήθειά σας για να υπολογίσει πόσες ομάδες θα χρειαστεί να φτιάξει.

Βάζετε λοιπόν τα δυνατά σας να τον βοηθήσετε. Είναι αδύνατο να μάθετε τους μυστικούς αριθμούς των επιστημόνων. Mε πολύ κόπο, καταφέρνετε να βρείτε μερικές δυάδες επιστημόνων που είναι φίλοι και για τους οποίους γνωρίζετε με βεβαιότητα ότι ο μυστικός αριθμός του πρώτου διαιρεί ακριβώς το μυστικό αριθμό του δεύτερου.

Mπορείτε να υπολογίσετε τον ελάχιστο αριθμό ομάδων που θα χρειαστεί να φτιάξει ο διοργανωτής του δείπνου;

Aρχεία εισόδου

Τα αρχεία εισόδου με όνομα scidinner.in είναι αρχεία κειμένου με την εξής δομή: Στην πρώτη γραμμή περιέχουν δύο φυσικούς αριθμούς \(N\) και \(M\) χωρισμένους με ένα κενό διάστημα (\(1 \leq M \leq N \leq 1.000.000\)), όπου \(N\) το πλήθος των επιστημόνων και \(M\) το πλήθος των δυάδων των φίλων. Θεωρούμε ότι οι επιστήμονες είναι αριθμημένοι από \(1\) έως και \(N\). Kάθε μία από τις επόμενες \(M\) γραμμές περιέχει δύο φυσικούς αριθμούς \(x_i\) και \(y_i\) χωρισμένους με ένα κενό διάστημα (\(1 \leq x_i, y_i \leq N\)), που ορίζουν μία δυάδα φίλων: γνωρίζουμε ότι ο μυστικός αριθμός του επιστήμονα xi διαιρεί ακριβώς το μυστικό αριθμό του επιστήμονα \(y_i\). Δε θα υπάρχουν δύο δυάδες με το ίδιο \(y_i\).

Aρχεία εξόδου

Τα αρχεία εξόδου με όνομα scidinner.out είναι αρχεία κειμένου με την εξής δομή: Έχουν ακριβώς μία γραμμή που περιέχει έναν ακέραιο αριθμό \(K\) (\(1 \leq K \leq N\)). Ο αριθμός αυτός εκφράζει το ελάχιστο πλήθος ομάδων επιστημόνων που πρέπει να φτιάξει ο διοργανωτής του δείπνου.

Παραδείγματα αρχείων εισόδου - εξόδου

1^o:

scidinner.in	scidinner.out
5 3 1 2 2 3 1 4	3

Εξήγηση: Θα χρειαστούν τουλάχιστον τρεις ομάδες (πιθανώς περισσότερες, ανάλογα με τους μυστικούς αριθμούς των επιστημόνων). Για παράδειγμα, αν οι μυστικοί αριθμοί είναι \(2\), \(4\), \(16\), \(10\) και \(3\) (κατά σειρά), μία δυνατή τοποθέτηση σε τρεις ομάδες είναι: \(\lbrace 2 \rbrace, \lbrace 16, 3\rbrace, \lbrace 4, 10\rbrace\).

2^o:

scidinner.in	scidinner.out
12 9 1 3 1 5 1 6 5 7 11 8 8 9 6 10 6 11 4 12	5

Mέγιστος χρόνος εκτέλεσης: \(1\) sec.