Θεωρία αριθμών για διαγωνισμούς πληροφορικής

Η θεωρία αριθμών είναι ο τομέας των μαθηματικών που μελετάει τις ιδιότητες των ακεραίων αριθμών. Αρκετά από τα θεωρήματα που περιέχονται στην θεωρία αριθμών μπορεί να είναι χρήσιμα και στην πληροφορική. Σε αυτή τη σελίδα θα αναφερόμαστε μόνο σε ακέραιους αριθμούς (και κυρίως σε φυσικούς).

• Πίνακας συμβόλων
• Υπόλοιπο
  • Πράξεις με υπόλοιπο
    • Πρόσθεση και πολλαπλασιασμός
    • Εύρεση δύναμης με υπόλοιπο
    • Πολλαπλασιαστικό αντίστροφο (διαίρεση)
• Πρώτοι αριθμοί
  • Ύπαρξη πρώτου διαιρέτη μικρότερου της ρίζας
  • Το μικρό θεώρημα του Fermat
    • Εύρεση πολλαπλασιαστικού αντιστρόφου
• Ο αλγόριθμος του Ευκλείδη
  • Επέκταση του αλγορίθμου του Ευκλείδη
  • Λύση Διοφαντικών εξισώσεων
  • Εύρεση πολλαπλασιαστικού αντιστρόφου
• Κόσκινα
  • Κόσκινο του Ερατοσθένη
  • Κόσκινο πολλαπλασιαστικών αντιστρόφων
• Γενικά
  • Επιπλέον για τους πρώτους
  • Επιπλέον κόσκινα
    • Παραγοντοποίηση αριθμού
  • Αποδείξεις
    • Απόδειξη του μικρού θεωρήματος του Fermat
    • Απόδειξη της πολυπλοκότητας του κόσκινου του Ερατοσθένη
• Προβλήματα
• Πηγές

Πίνακας συμβόλων

Υπόλοιπο

Σύμφωνα με την Ευκλείδεια διαίρεση, όταν διαιρούμε τον διαιρετέο $n$ με τον διαιρέτη $d$, υπάρχει μοναδικό πηλίκο $k$ και υπόλοιπο $m$ έτσι ώστε $n=kd+m$, με $m<d$. Θα γράφουμε $n \equiv m \pmod{d}$ (το $n$ είναι ισοϋπόλοιπο του $m$ διά του $d$) και $m = n \bmod d$ (το $m$ ισούται με το υπόλοιπο της διαίρεσης του $n$ με το $d$).

Πράξεις με υπόλοιπο

Σε πολλά προβλήματα μας ζητείται να επιστρέψουμε το αποτέλεσμα μιας πράξης με κάποιο υπόλοιπο, δηλαδή δίνεται κάποιο $d$, και αν το αποτέλεσμα του αλγορίθμου μας ήταν $n$, μας ζητείται να επιστρέψουμε τον αριθμό $n \bmod d$.

Πρόσθεση και πολλαπλασιασμός

Η πρόσθεση, η αφαίρεση και ο πολλαπλασιασμός γίνονται κανονικά όταν έχουμε τον ίδιο διαιρέτη. Δηλαδή:

$(a+b) \bmod d = ((a \bmod d)+(b \bmod d)) \bmod d\\(a-b) \bmod d =((a \bmod d)-(b \bmod d)+d) \bmod d\\(ab) \bmod d=((a \bmod d)\times(b \bmod d)) \bmod d$.

Εύρεση δύναμης με υπόλοιπο

Αν και αυτός ο αλγόριθμος δεν αφορά μόνο τις περιπτώσεις που θέλουμε τη δύναμη ενός αριθμού με υπόλοιπο κάποιον άλλον αριθμό, σε αυτές τις περιπτώσεις είναι πιο χρήσιμος. Είναι ένας αναδρομικός αλγόριθμος, που για να υπολογίσει τη δύναμη ενός αριθμού $n$ στον εκθέτη $k$ με υπόλοιπο $m$, χρειάζεται $O(\log k)$ πράξεις.

int powmod(int base, int exp, int mod) {
    if(exp==0) {
        return 1;
    }
    long long half=powmod(base, exp/2, mod);
    if(exp%2==0) {
        return half*half%mod;
    }
    else {
        return half*half*base%mod;
    }
}

Πολλαπλασιαστικό αντίστροφο (διαίρεση)

Δυστυχώς, η διαίρεση δεν είναι το ίδιο απλή με τις υπόλοιπες πράξεις. Θα ορίσουμε το πολλαπλασιαστικό αντίστροφο με υπόλοιπο $a^{-1}$ ενός αριθμού $a$, ως τον (ακέραιο πάντα) αριθμό μικρότερο του $d$ (όπου $d$ είναι ο διαιρέτης), για τον οποίο ισχύει $a^{-1}a \equiv 1 \pmod{d}$. Για παράδειγμα, το πολλαπλασιαστικό αντίστροφο του 2, για $d=3$ είναι το 2, αφού $2\times 2 = 4 \equiv 1 \pmod{3}$. Υπάρχουν περιπτώσεις όμως που δεν υπάρχει πολλαπλασιαστικό αντίστροφο. Για παράδειγμα, για $d=4$, ο αριθμός 2 δεν έχει πολλαπλασιαστικό αντίστροφο. Ισχύει όμως ότι όταν ο διαιρέτης $d$ είναι πρώτος αριθμός, τότε πάντα υπάρχει πολλαπλασιαστικό αντίστροφο. Από εδώ και πέρα θα αναφερόμαστε σε πολλαπλασιαστικό αντίστροφο μόνο για πρώτους αριθμούς.

Πρώτοι αριθμοί

Οι πρώτοι αριθμοί λέγονται οι φυσικοί αριθμοί οι οποίοι διαιρούνται μόνο από τον εαυτό τους και το $1$. Πρώτοι αριθμοί είναι οι $2, 3, 5, 7, 11, 13, \ldots$

Ισχύει ότι όλοι οι ακέραιοι αριθμοί μπορούν να γραφούν με μοναδικό τρόπο ως γινόμενο δυνάμεων πρώτων αριθμών.

Ύπαρξη πρώτου διαιρέτη μικρότερου της ρίζας

Δηλαδή, εάν ένας αριθμός $n$ δεν είναι πρώτος, τότε υπάρχει ένας πρώτος $p$ έτσι ώστε $p \nmid n$ και $p^2\leq n$.

Η απόδειξη είναι ιδιαίτερα εύκολη. Έστω ότι όλοι οι πρώτοι διαιρέτες ενός αριθμού είναι καθαρά μεγαλύτεροι της ρίζας του. Αφού ο αριθμός δεν είναι πρώτος, τότε θα υπάρχουν τουλάχιστον δύο (όχι απαραίτητα διαφορετικοί, αλλά τέτοιο ώστε το γινόμενό τους να διαιρεί το $n$) πρώτοι αριθμοί που τον διαιρούν, έστω $p_1,p_2$. Τότε, $p_1p_2 > \sqrt{n}\sqrt{n} = n$, άτοπο αφού αναγκαστικά ισχύει $p_1p_2\leq n$.

Από αυτό το αποτέλεσμα έχουμε έναν γρήγορο και εύκολο τρόπο να ελέγξουμε αν ένας αριθμός είναι πρώτος, διότι αρκεί να ελέγξουμε εάν τον διαιρεί κάποιος αριθμός ο οποίος είναι μικρότερος ή ίσος της ρίζας του. Επομένως, για έναν αριθμό $n$, μπορούμε να ελέγξουμε σε χρόνο $O(\sqrt{n})$ εάν είναι πρώτος.

bool is_prime(int n) {
    if(n==0 || n==1) {
        return false;
    }
    for(int i=2; i<=sqrt(n); ++i) {
        if(n%i==0) {
            return false;
        }
    }
    return true;
}

Το μικρό θεώρημα του Fermat

Σύμφωνα με το μικρό θεώρημα του Fermat, εάν $p$ πρώτος και $n$ ακέραιος, όχι πολλαπλάσιο του $p$, τότε $n^{p-1} \equiv 1 \pmod{p}$.

Εύρεση πολλαπλασιαστικού αντιστρόφου

Χρησιμοποιώντας αυτό το αποτέλεσμα, μπορούμε εύκολα να βρούμε το πολλαπλασιαστικό αντίστροφο ενός αριθμού n, όταν ο διαιρέτης είναι πρώτος. Να υπενθυμίσουμε ότι στην περίπτωση που ο διαιρέτης είναι πρώτος, υπάρχει πάντα πολλαπλασιαστικό αντίστροφο. Έχουμε ότι $n^{p-1}\equiv 1\pmod{p} \Leftrightarrow n^{p-2}\equiv n^{-1}\pmod{p}$. Είναι εμφανές ότι η πολυπλοκότητα του αλγορίθμου είναι $O(\log p)$.

int invmod(int num, int mod) {
    return powmod(num, mod-2, mod);
}

Ο αλγόριθμος του Ευκλείδη

Ο αλγόριθμος του Ευκλείδη είναι ένας αλγόριθμος εύρεσης του ΜΚΔ (μέγιστου κοινού διαιρέτη) δύο αριθμών. Να σημειωθεί ότι για την εύρεση του μέγιστου κοινού διαιρέτη δύο αριθμών $a,b$ μπορούμε να χρησιμοποιήσουμε την εντολή της c/c++, __gcd(a,b). Μια χρήσιμη ιδιότητα του μέγιστου κοινού διαιρέτη είναι ότι μπορούμε να τον χρησιμοποιήσουμε για να βρούμε το ελάχιστο κοινό πολλαπλάσιο αφού το γινόμενο του μέγιστου κοινού διαιρέτη και του ελάχιστου κοινού πολλαπλασίου ισούται με το γινόμενο των αριθμών.

Ο αλγόριθμος του Ευκλείδη βασίζεται στο γεγονός ότι $\gcd(a,b)=\gcd(a\bmod{b}, b)$. Αυτό βασίζεται στο γεγονός ότι $a \bmod b = a - \left \lfloor \frac{a}{b} \right \rfloor$. Αν $b\leq a$, τότε $a\bmod{b} < a$, επομένως θα χρειαστεί πεπερασμένος αριθμός βημάτων, αφού σε κάθε βήμα μικραίνει ένας από τους δύο αριθμούς. Όταν φτάσουμε στο σημείο όπου $a=0$ ή $b=0$, γνωρίζουμε απευθείας τον μέγιστο κοινό διαιρέτη. Αποδεικνύεται ότι τα βήματα που χρειάζεται ο αλγόριθμος του Ευκλείδη για να βρει τον μέγιστο κοινό διαιρέτη είναι $O(\log\min(a,b))$. Προσοχή να φροντίζουμε να έχουμε τον μικρότερο αριθμό δεύτερο έτσι ώστε πράγματι να μικραίνει ένας από τους δύο αριθμούς σε κάθε βήμα.

int gcd(int a, int b) {
    if(b==0) {
        return a;
    }
    else {
        return gcd(b, a%b);
    }
}
long long lcm(int a, int b) {
    return (long long)a/(long long)gcd(a,b)*(long long)b;
}

Ο λόγος που γράψαμε a/gcd(a,b)*b και όχι a*b/gcd(a,b) είναι για να αποφύγουμε την περίπτωση που η τιμή του $ab$ υπερβαίνει την μέγιστη τιμή ακεραίου, αλλά η τιμή $\frac{ab}{\gcd(a,b)}$ δεν την υπερβαίνει. Επίσης το θέσαμε ως long long γιατί υπάρχει η περίπτωση οι αριθμοί να είναι πρώτοι μεταξύ τους, οπότε το ελάχιστο κοινό πολλαπλάσιο θα ισούται με το γινόμενό τους και ο αριθμός αυτός θα είναι πολύ μεγάλος για να χωρέσει σε int.

Επέκταση του αλγορίθμου του Ευκλείδη

Ο αλγόριθμος του Ευκλείδη μπορεί να επεκταθεί έτσι ώστε να βρει ακέραιες λύσεις για τα $x,y$ στην εξίσωση $ax+by=\gcd(a,b)$.

Είδαμε ήδη ότι $\gcd(b\bmod a, a) = \gcd(a,b)$. Ας υποθέσουμε ότι έχουμε βρει μια λύση $x_0,y_0$ στην εξίσωση $(b\bmod a)x_0+ay_0=\gcd(a,b)$, και ψάχνουμε τη λύση $x_1,y_1$ στην εξίσωση $ax+by=\gcd(a,b)$. Γράφουμε $\gcd(a,b)=(b\bmod a)x_0+ay_0 = (b-\left \lfloor \frac{b}{a} \right \rfloor a)x_0+ay_0 = bx_0+a(y_0-\left \lfloor\frac{b}{a}\right \rfloor x_0)$. Οπότε έχουμε ότι $x_1=y_0-\left \lfloor \frac{b}{a} \right \rfloor x_0$ και $y_1=x_0$.

struct gcd_tuple {
    int x, y, g;
};
gcd_tuple ext_gcd(int a, int b) {
    gcd_tuple out;
    if(a==0) {
        out.x=0;
        out.y=1;
        out.g=b;
        return out;
    }
    gcd_tuple prev=ext_gcd(b%a, a);
    out.x=prev.y-b/a*prev.x;
    out.y=prev.x;
    out.g=prev.g;
    return out;
}

Λύση Διοφαντικών εξισώσεων

Οι Διοφαντικές εξισώσεις είναι εξισώσεις στους ακεραίους αριθμούς της μορφής $ax+by=c$, όπου οι άγνωστοι είναι τα $x,y$. Προφανώς αν $a=b=c=0$ τότε υπάρχουν άπειρες λύσεις και αν $a=b=0, c\neq0$ δεν υπάρχει καμία λύση. Ισχύει ότι οι Διοφαντικές εξισώσεις έχουν λύση αν και μόνο αν $\gcd(a,b)\mid c$. Μπορούμε λοιπόν να λύσουμε μια Διοφαντική εξίσωση με τη χρήση της επέκτασης του αλγορίθμου του Ευκλείδη.

struct diof_tuple {
    int x, y;
    bool has_sol;
};
diof_tuple solve_diof(int a, int b, int c) {
    diof_tuple out;
    gcd_tuple g=ext_gcd(a,b);
    if((g.g==0 && c!=0) || c%g.g!=0) {
        out.has_sol=false;
        return out;
    }
    if(g.g==0) {
        out.has_sol=false;
        return out;
    }
    out.x=g.x*(c/g.g);
    out.y=g.y*(c/g.g);
    if(a<0) {
        out.x*=-1;
    }
    if(b<0) {
        out.y*=-1;
    }
    out.has_sol=true;
    return out;
}

Εάν θέλουμε να βρούμε όλες τις λύσεις μιας Διοφαντικής εξίσωσης μπορούμε να χρησιμοποιήσουμε το γεγονός ότι αν έχουμε μια λύση $x_0,y_0$, τότε για κάθε ακέραιο $k$, ισχύει ότι κάθε ζευγάρι $x=x_0+k\frac{b}{\gcd(a,b)}, y=y_0-k\frac{a}{\gcd(a,b)}$ εξακολουθεί να είναι λύση της Διοφαντικής εξίσωσης.

Εύρεση πολλαπλασιαστικού αντιστρόφου

Υπενθυμίζουμε ότι το πολλαπλασιαστικό αντίστροφο ενός αριθμού $a$ ως προς διαιρέτη $m$ είναι ο φυσικός αριθμός $a^{-1}$ για τον οποίο ισχύει ότι $a^{-1}a\equiv 1 \pmod{m}$ και αυτός ο αριθμός υπάρχει αν και μόνο αν $m\nmid a$. Ας θεωρήσουμε την Διοφαντική εξίσωση $ax+my=1$. Ήδη γνωρίζουμε ότι $\gcd(a,m)=1$, αφού $m\nmid a$. Άρα αρκεί να χρησιμοποιήσουμε την επέκταση του αλγορίθμου του Ευκλείδη για να λύσουμε την εξίσωση αυτή, η οποία ήδη ξέρουμε πως έχει τουλάχιστον μία λύση. Τότε, θα ισχύει ότι $ax=1-my \Rightarrow ax\equiv 1 \pmod{m}$, επομένως θα έχουμε βρει το πολλαπλασιαστικό αντίστροφο του $a$.

int invmod(int num, int mod) {
    gcd_tuple g=ext_gcd(num, mod);
    if(g.g!=1) {
        return 0;
    }
    return (g.x%mod+mod)%mod;
}

Κόσκινα

Κόσκινο του Ερατοσθένη

Το κόσκινο του Ερατοσθένη βρίσκει όλους τους πρώτους μέχρι κάποιο όριο $N$. Η πολυπλοκότητά του είναι $O(N\log\log N)$. Εάν γνωρίζουμε όλους τους πρώτους μέχρι κάποιον αριθμό $k$, τότε γνωρίζουμε ότι όλα τους τα πολλαπλάσια δεν είναι πρώτοι. Αν γράψουμε σε έναν πίνακα όλους τους αριθμούς μέχρι το $N$ και σβήσουμε τα πολλαπλάσια των γνωστών πρώτων, τότε οι αριθμοί που θα απομείνουν πρέπει αναγκαστικά να περιέχουν πρώτους. Μάλιστα, ο ελάχιστος από τους εναπομείναντες αριθμούς θα πρέπει να είναι πρώτος, διότι δεν τον διαιρεί κανένας άλλος αριθμός εκτός από τον εαυτό του και το 1. Άρα, έχουμε αποκτήσει έτσι έναν καινούριο πρώτο αριθμό, και μπορούμε να συνεχίσουμε τη διαδικασία αυτή μέχρι να βρούμε όλους τους πρώτους μέχρι το $N$. Ας δούμε ένα παράδειγμα, όπου $N=20$:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

2 3 5 7 9 11 13 15 17 19

2 3 5 7 11 13 17 19

bool notprime[MAXN];
vector<int> prime_sieve(int n) {
    vector<int> primes;
    for(int i=2; i<=n; ++i) {
        if(notprime[i]) {
            continue;
        }
        primes.push_back(i);
        for(int j=2*i; j<=n; j+=i) {
            notprime[j]=true;
        }
    }
    return primes;
}

Κόσκινο πολλαπλασιαστικών αντιστρόφων

Με αυτό το κόσκινο μπορούμε να βρούμε όλα τα πολλαπλασιαστικά αντίστροφα των αριθμών σε $O(p)$, όπου $p$ είναι ο διαιρέτης. Εάν $p$ είναι ο (πρώτος) διαιρέτης και $i$ είναι ο αριθμός για τον οποίο θέλουμε να υπολογίσουμε το πολλαπλασιαστικό αντίστροφο, έχοντας ήδη υπολογίσει το πολλαπλασιαστικό αντίστροφο για όλους τους αριθμούς μέχρι το $i-1$. Ισχύει ότι:

Γνωρίζουμε ότι ο αριθμός $\left \lfloor \frac{p}{i}\right \rfloor$ είναι ακέραιος, και ότι $p\bmod i < i$, επομένως το αντίστροφο του αριθμού αυτού το έχουμε ήδη υπολογίσει.

int inv[MAXN];
void inverse_sieve(int mod) {
    inv[1]=1;
    for(int i=2; i<mod; ++i) {
        inv[i]=(mod-mod/i*inv[mod%i]%mod)%mod;
    }
}
int invmod(int num, int mod) {
    return inv[(num%mod+mod)%mod];
}

Να σημειωθεί ότι στην περίπτωση όπου ο $p$ δεν είναι πρώτος, ο αλγόριθμος αυτός εξακολουθεί να είναι σωστός (σε αντίθεση με τον αλγόριθμο που βασίζεται στο μικρό θεώρημα του Fermat), αλλά όταν δεν υπάρχει πολλαπλασιαστικό αντίστροφο για κάποιον αριθμό $i$, τότε inv[i]=0.

Γενικά

Επιπλέον για τους πρώτους

Σύμφωνα με το Θεώρημα Πρώτων Αριθμών, το πλήθος των πρώτων μέχρι τον $n$ έχει τάξη μεγέθους $O\left (\frac{n}{\log n}\right)$.

Επίσης ισχύει ότι εάν $p$ πρώτος αριθμός και $p\nmid n, n\nmid p$, τότε οι δυνάμεις του $n$ με υπόλοιπο το $p$ παίρνουν κυκλικά όλες τις θετικές τιμές μικρότερες του $p$. Δηλαδή $n^i\equiv n^j \pmod{p} \Leftrightarrow i\equiv j \pmod{p-1}$.

Επιπλέον κόσκινα

Παραγοντοποίηση αριθμού

Ήδη γνωρίζουμε ότι όλοι οι ακέραιοι μπορούν να παραγοντοποιηθούν με μοναδικό τρόπο. Ας εξετάσουμε το πρόβλημα της παραγοντοποίησης αριθμού. Η προφανής λύση είναι να χρησιμοποιήσουμε το κόσκινο του Ερατοσθένη και να το εφαρμόσουμε για να παραγοντοποιήσουμε τους αριθμούς. Αλλά ας δούμε πώς μπορούμε να μετατρέψουμε το κόσκινο του Ερατοσθένη για να λύσουμε το συγκεκριμένο αυτό πρόβλημα. Θα δημιουργήσουμε ένα κόσκινο έτσι ώστε να ξέρουμε τον ελάχιστο πρώτο που διαιρεί τον κάθε ακέραιο. Εάν γνωρίζουμε για κάθε αριθμό τον ελάχιστο πρώτο που τον διαιρεί, τότε μπορούμε να προχωρήσουμε αναδρομικά μέχρι να φτάσουμε στον αριθμό 1.

Για να φτιάξουμε αυτό το κόσκινο, θα κάνουμε την ίδια διαδικασία με το κόσκινο του Ερατοσθένη, αλλά κάθε φορά που σημειώνουμε ότι ένας αριθμός δεν είναι πρώτος, αντί για αυτό θα ενημερώνουμε τον ελάχιστο πρώτο που τον διαιρεί.

int mnprime[MAXN];
void div_sieve(int n) {
    for(int i=1; i<=n; ++i) {
        mnprime[i]=i;
    }
    for(int i=2; i<=n; ++i) {
        if(mnprime[i]<i) {
            continue;
        }
        for(int j=2*i; j<=n; j+=i) {
            mnprime[j]=min(mnprime[j], i);
        }
    }
}
vector<int> factor(int val) {
    vector<int> out;
    while(val>1) {
        out.push_back(mnprime[val]);
        val/=mnprime[val];
    }
    return out;
}

Αποδείξεις

Απόδειξη του μικρού θεωρήματος του Fermat

Έστω ο πρώτος $p$, και ο ακέραιος $n$, έτσι ώστε $n \not\equiv 0 \pmod{p}$. Θεωρούμε τα πρώτα $p$ πολλαπλάσια του $n$, τα οποία είναι τα $n, 2n, 3n, \ldots, (p-1)n$. Εάν υπάρχουν δύο μεταξύ τους τα οποία είναι ισοϋπόλοιπα του $p$, τότε έχουμε ότι υπάρχει $i$ και $j$ έτσι ώστε $in\equiv jn \pmod{p} \xrightarrow{n\not\equiv 0\pmod{p}} i\equiv j \pmod{p} \xrightarrow{i,j<p} i=j$, άτοπο. Παρομοίως δεν υπάρχει κανένα $i$ έτσι ώστε $in\equiv 0 \pmod{p}$, διότι $n\not\equiv 0 \pmod{p}$ και $i\not\equiv 0 \pmod{p}$ για κάθε $i$. Επομένως όλα αυτά τα πολλαπλάσια έχουν διαφορετικό υπόλοιπο με διαιρέτη τον $p$, και αφού τα μη μηδενικά υπόλοιπα του $p$ είναι $p-1$ σε πλήθος, όπως και τα πολλαπλάσια, αναγκαστικά θα υπάρχει κάποια 1 προς 1 αντιστοιχία μεταξύ των πολλαπλασίων του $n$ και των υπολοίπων του $p$. Άρα, $n\times2n\times3n\times\ldots\times(p-1)n \equiv 1\times2\times3\times\ldots\times(p-1) \pmod{p} \Leftrightarrow \\(p-1)!n^{p-1}\equiv (p-1)!\pmod{p} \Leftrightarrow n^{p-1}\equiv 1\pmod{p}$

Απόδειξη της πολυπλοκότητας του κόσκινου του Ερατοσθένη

Θα χρησιμοποιήσουμε το εξής χωρίς απόδειξη: $\sum_{p \in P}^{p \leq n} {\frac{1}{p}}=\Theta(\ln\ln{n})$, όπου $P$ είναι το σύνολο των πρώτων. Για τον κάθε πρώτο $i$, εξετάζουμε όλα του τα πολλαπλάσια μέχρι το $n$. Επομένως, κάνουμε $\frac{n}{i}$ πράξεις για κάθε $i$. Εάν αθροίσουμε αυτούς τους αριθμούς έχουμε ότι θα κάνουμε $\sum_{i\in P}^{i\leq n} {\frac{n}{i}} = n\sum_{i\in P}^{i\leq n} {\frac{1}{i}} = \Theta(n\ln\ln n)$ πράξεις.

Ένα άλλο χρήσιμο αποτέλεσμα γενικότερα για τα κόσκινα είναι ότι $\sum_{i=1}^{i\leq n} {\frac{1}{i}}=O(\ln n)$.

Προβλήματα

GAMES (Spoj)

NDIV (Spoj)

Prevdiv (23ος πδπ)

Strategy (2014 Jboi)

Couple Cover (Codeforces)

GCD Table (Codeforces)

Mashmokh and ACM (Codeforces)

Rare Easy Problem (UVa)

Play with Floor and Ceil (UVa)

Marbles (UVa)

Πηγές

http://codeforces.com/blog/entry/8989

http://e-maxx.ru/algo/diofant_2_equation (μέσω google translate)

Σχόλια