38ος ΠΔΠ : Μέγιστος γνήσιος διαιρέτης (gpd) - Λύση

Επεξήγηση εκφώνησης

Μας δίνονται κάποιοι σύνθετοι αριθμοί $G$. Πρέπει να απαντήσουμε ερωτήσεις της μορφής “πόσοι αριθμοί έχουν το $G$ ως μέγιστο γνήσιο διαιρέτη”.

Παρατήρηση: Έστω ένας φυσικός αριθμός $x$ και $p$ ο μικρότερος πρώτος αριθμός που τον διαιρεί. Τότε, ο μέγιστος γνήσιος διαιρέτης του αριθμού είναι ο $G = x/p$.

(Αιτιολόγηση) Γράφουμε $x = p_1\cdot p_2 \cdot \ldots \cdot p_k$ όπου $p_1 \leq p_2 \leq \ldots \leq p_k$ πρώτοι αριθμοί. Έστω $G$ ένας γνήσιος διαιρέτης του $x$, δηλαδή $x = G \cdot y$ για κάποιον $y$. Τότε ο $G$ είναι μέγιστος όταν ο $y$ είναι ελάχιστος. Ο $y$ έχει ως πρώτους παράγοντες κάποιο υποσύνολο αυτών του $x$. Άρα ελαχιστοποιείται όταν $y = p_1$ και $G = x/p_1$.

Με αυτή την παρατήρηση οι ερωτήσεις “πόσοι από τους αριθμούς $2G, 3G, 4G, 5G,\ldots$ έχουν τον $G$ ως μέγιστο γνήσιο διαιρέτη” είναι ισοδύναμες με

“Πόσοι από τους $2, 3, 4, 5, \ldots, p$ δεν έχουν κάποιον πρώτο παράγοντα μικρότερο από τον μικρότερο του $G$, έστω $p$”

που είναι ισοδύναμες με

“Πόσοι από τους πρώτους αριθμούς μικρότεροι από $p$ είναι πρώτοι”

Βέλτιστη λύση

Για την βέλτιση λύση θα χρησιμοποιήσουμε μία παραλλαγή του κόσκινου του Ερατοσθένη. Για $T = 10^8$, θα υπολογίσουμε

prime_factor[x]: τον μικρότερο πρώτο παράγοντα του x για κάθε $x \leq T$.
cnt_primes[x]: το πλήθος των πρώτων αριθμών μικρότερων ή ίσων του x για κάθε $x \leq T$.
primes: τους πρώτους αριθμούς μέχρι $T$

Λύση για μικρούς αριθμούς

Το κόσκινο του Ερατοσθένη είναι ένας αλγόριθμος για την εύρεση των πρώτων αριθμών που είναι μικρότεροι από έναν δοσμένο ακέραιο $T$. Διατηρεί έναν πίνακα από δυαδικές τιμές που κάθε μία μας λέει αν ένας αριθμός είναι πρώτος ή όχι. Αρχικά όλες οι τιμές είναι αληθής. Έπειτα, ξεκινάει με το $2$ και διαγράφει όλα τα πολλαπλάσια του από τον πίνακα (δηλαδή θέτει τις τιμές στις θέσεις $2\cdot 2, 3 \cdot 2, 4 \cdot 2, \ldots$$ σε $0$), έπειτα συνεχίζει με τα πολλαπλάσια του $3$, τα πολλαπλάσια του $5$ και γενικά τα πολλαπλάσια του κάθε αριθμού που δεν έχει διαγραφεί ως εκείνη την στιγμή.

Κάνουμε την εξής απλή αλλά χρήσιμη παρατήρηση:

Παρατήρηση: Κάθε σύνθετος αριθμός θα διαγραφεί για πρώτη φορά από τον μικρότερο πρώτο παράγοντά του.

Επομένως, μπορούμε να χρησιμοποιήσουμε το κόσκινο του Ερατοσθένη για να βρούμε τον μικρότερο πρώτο παράγοντα ενός αριθμού. Για να απαντήσουμε γρήγορα πόσοι είναι οι πρώτοι αριθμοί μικρότεροι από $p$ υπολογίζουμε αθροίσματα προθέματος (prefix sums) στον πίνακα cnt_primes. Παρακάτω δίνεται η υλοποίηση:

  // Βρίσκουμε τον μέγιστο γνήσιο διαιρέτη για κάθε μικρό αριθμό.
  long prime_idx = 0;
  for (long i = 2; i < T; ++i) {
    cnt_primes[i] = cnt_primes[i-1];
    if (prime_factor[i] != 0) continue;
    ++cnt_primes[i];
    primes[prime_idx] = i;
    ++prime_idx;
    for (long j = i * i; j < T; j += i) {
      if (prime_factor[j] == 0) prime_factor[j] = i;
    }
  }

Το κόσκινο του Ερατοσθένη έχει πολυπλότητα $\mathcal{O}(T \log \log T)$. Θα χρησιμοποιήσουμε αυτή την μέθοδο για να απαντήσουμε ερωτήματα που το $G \leq 10^8$.

Λύση για μεγάλους αριθμούς

Για μεγαλύτερα $G$ που ξέρουμε ότι θα είναι το πολύ $5.000$ θα βρούμε τον μικρότερο πρώτο του παράγοντα διαιρώντας με όλους τους πρώτους που έχουμε υπολογίσει. Αφού ο αριθμός είναι σύνθετος $G = mn$, ξέρουμε ότι ένας από τους δύο διαιρέτες του είναι το πολύ $\sqrt{G}\leq \sqrt{10^{12}} = 10^6$. Επομένως ένας πρώτος παράγοντάς του θα είναι σε αυτούς που υπολογίσαμε με το κόσκινο του Ερατοσθένη. Διατρέχοντας όλους τους πρώτους αριθμούς, βρίσκουμε αυτόν τον παράγοντα σε χρόνο περίπου $\mathcal{O}(\sqrt{G})$ (αλλά στην πράξη είναι πιο γρήγορο από το να κοιτάξουμε όλους τους αριθμούς $2, 3, \ldots, \sqrt{G}$).

      for (long j = 0; j <= prime_idx; ++j) {
        if (G % primes[j] == 0) {
          smallest_prime_factor = primes[j];
          break;
        }
      }

Συνδυάζοντας αυτές τις δύο μεθόδους είναι αρκετό για να περάσει όλα τα testcases. Μπορείτε να βρείτε ολόκληρο τον κώδικα εδώ.