29ος ΠΔΠ Καμπ (κοινά)
Μέγιστος κοινός διαιρέτης (gcdseq)

Συμβαίνει σε πολλούς να βαριούνται στην τάξη, αλλά το σημερινό δεν έχει προηγούμενο. Η κοπέλα του ήρωά μας, Ευρυδίκη, είναι πολύ απορροφημένη στο μάθημα, κι η δασκάλα τού πήρε και το στυλό για να σταματήσει να ζωγραφίζει γάτες. Μην ξέροντας τι να κάνει, το παλικάρι μας πρέπει να διαλέξει μεταξύ δύο επιλογών. Είτε να παίξει ναρκαλιευτή, είτε να προσέξει στο μάθημα. Δυστυχώς ποτέ δεν έμαθε να παίζει ναρκαλιευτή (πάντα πατούσε στην τύχη τα τετράγωνα), κι έτσι αποφάσισε να προσέξει κι αυτός την παράδοση. Το πρόβλημα που η τάξη έλυνε εκείνη τη στιγμή ήταν το εξής:

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

Ευτυχώς ο ήρωάς μας θυμάται ακόμα πώς να βρίσκει το μέγιστο κοινό διαιρέτη δύο αριθμών με τον αλγόριθμο του Ευκλείδη:

int gcd(int a, int b) {
   if (min(a,b) == 0) return max(a,b);
   return gcd(b, a%b);
}

Μπορείς να βοηθήσεις τον πρωταγωνιστή μας να ξαναμπεί δυναμικά στο μάθημα;

Δεδομένα εισόδου (gcdseq.in)

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

Δεδομένα εξόδου (gcdseq.out)

Η έξοδος πρέπει να περιέχει μία γραμμή με ακριβώς έναν φυσικό αριθμό: το μέγιστο πλήθος συνεχόμενων αριθμών της ακολουθίας που έχουν μέγιστο κοινό διαιρέτη μεγαλύτερο του \(1\).

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

gcdseq.in	gcdseq.out
4 3 8 4 7	2

Εξήγηση: Τα συνεχόμενα διαστήματα με μέγιστο κοινό διαιρέτη μεγαλύτερο του \(1\) είναι τα: \(\{3\}, \{8\}, \{4\}, \{7\}, \{8, 4\}\). Το μεγαλύτερο από αυτά είναι το \(\{8,4\}\), με πλήθος στοιχείων \(2\).

Περιορισμοί

Κάθε αριθμός της ακολουθίας θα είναι μικρότερος του \(1.000.000.000\).
Όριο χρόνου εκτέλεσης: \(1\) sec.
Όριο μνήμης: \(64\) MB.

Υποπροβλήματα