Αρχική > 38ος ΠΔΠ

38ος ΠΔΠ B' Φάση
Μέγιστος γνήσιος διαιρέτης (gpd)

Όσο εσείς λύνατε τα “Δυαδικά Ερωτήματα” της Α’ Φάσης, ο Τάκης σκέφτηκε ακόμα ένα όμορφο θέμα, όπως σας είχε υποσχεθεί.

Λίγη ορολογία πρώτα. Έστω \(K\) και \(G\) θετικοί ακέραιοι αριθμοί. Λέμε ότι ο \(K\) είναι ένας γνήσιος διαιρέτης του \(G\), αν ο \(K\) διαιρεί τον \(G\) και επιπλέον \(K \neq G\). Λέμε ότι ο \(G\) είναι σύνθετος αριθμός όταν υπάρχει τουλάχιστον ένας γνήσιος διαιρέτης του \(G\) μεγαλύτερος του \(1\).

Ο Τάκης έχει μαζέψει \(Q\) ερωτήματα, όπου κάθε ερώτημα αποτελείται από έναν σύνθετο θετικό ακέραιο \(G\). Η απάντηση ενός τέτοιου ερωτήματος είναι το πλήθος των θετικών ακεραίων \(x\) για τους οποίους ισχύει ότι ο \(G\) είναι ο μέγιστος γνήσιος διαιρέτης του \(x\).

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

Δεδομένα εισόδου (stdin)

Η πρώτη γραμμή περιέχει έναν ακέραιο αριθμό \(Q\): το πλήθος των ερωτημάτων του Τάκη. Ακολουθούν \(Q\) γραμμές, καθεμία από τις οποίες περιέχει έναν ακέραιο αριθμό \(G_i\): το \(i\)-οστό ερώτημα.

Δεδομένα εξόδου (stdout)

Πρέπει να αποτελείται από \(Q\) γραμμές, καθεμία από τις να περιέχει έναν ακέραιο αριθμό: την απάντηση στο \(i\)-οστό ερώτημα.

Παράδειγμα εισόδου-εξόδου

stdin stdout
3
6
53357
250019000261		 1
50
41539

Εξήγηση παραδείγματος: Για το πρώτο ερώτημα, μπορεί να αποδειχθεί ότι ο μόνος αριθμός του οποίου ο μέγιστος γνήσιος διαιρέτης είναι ίσος με \(6\), είναι το \(12\).

Περιορισμοί

  • \(1 \leq Q \leq 200.000\).
  • \(4 \leq G_i \leq 10^{12}\).
  • Ο \(G_i\) είναι σύνθετος, για κάθε \(i\) (όπου \(1 \leq i \leq Q\)).
  • Ισχύει ότι \(G_i > 10^7\), για το πολύ \(5.000\) από τα \(Q\) ερωτήματα.

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

  1. (18 βαθμοί) Ο \(G_i\) είναι άρτιος, για κάθε \(i\) (όπου \(1 \leq i \leq Q\)).
  2. (23 βαθμοί) \(Q \leq 50.000\), \(G_i \leq 10^7\), για κάθε \(i\) (όπου \(1 \leq i \leq Q\)).
  3. (32 βαθμοί) \(G_i \leq 10^7\), για κάθε \(i\) (όπου \(1 \leq i \leq Q\)).
  4. (27 βαθμοί) Δεν υπάρχουν περαιτέρω περιορισμοί.

Παρατηρήσεις

Μέγιστος χρόνος εκτέλεσης: \(2\) sec.
Μέγιστη διαθέσιμη μνήμη: \(128\) MB.