Maximum Prime Factor
Problem
Θέλουμε να πάμε από τον αριθμό \(Χ\) στον αριθμό \(Y\) κάνοντας ένα από τα ακόλουθα operations:
Έστω \(p\) ο μεγαλύτερος πρώτος διαιρέτης του \(Χ\).
-
Να διαιρέσουμε το \(Χ\) με το \(p\) άρα το \(X\) γίνεται \(X/p\).
-
Να πολλαπλασιάσουμε το \(Χ\) με κάποιο πρώτο αριθμό \(k\) όπου \(p \le k\) άρα το \(X\) γίνεται \(X \cdot k\)
Solution
Subtask 1 (24 points)
\(1 \le X,Y,Q \le 1000\) Αυτό το subtask λύνεται με dynamic programming και κάποια observations όμως πιστεύω πως αν σκεφτήτε τα observations μπορείτε πιο εύκολα να πάρετε τα πρώτα 2 subtasks.
Subtask 2 (72 points)
\(1 \le X,Y,Q \le 10^5\)
Αν πηγαίνοντας από τον μικρότερο πρώτο αριθμό στον μεγαλύτερο (ας τον ονομάζουμε \(i\)) έστω \(a\) η μεγαλύτερη δύναμη του \(i\) που διαιρεί το \(Χ\) και έστω \(b\) η μεγαλύτερη δύναμη του \(i\) που διαιρεί το \(Y\).
Αν \(i\) δεν διαιρεί ούτε το \(Χ\) ούτε το \(Y\) τότε δεν υπάρχει λόγος να το ελέγξουμε.
Case \(1\): \(a = b\)
Δεν χρειάζεται να διαιρέσουμε/πολλαπλασιάσουμε με κάτι άρα συνεχίζουμε στο επόμενο \(i\).
Case \(2\): \(a > b\)
Αναγκαστηκά πρέπει να φύγουμε όλες τις εμφανίσεις των πρώτων διαιρετών του \(Χ\) που είναι \(> i\) καθώς και να φύγουμε \(a - b\) φορές το \(i\). Όταν τους διαγράψουμε διαιρώντας το \(Χ\) με αυτούς θα έχουμε όλους τους πρώτους \(\le i\) στο \(Χ\) ίσες φορές με το \(Y\) (\(a = b\) για όλους τους πρώτους \(\le i\)) και δεν έχουμε άλλους πρώτους στο \(X\) (αφού διαγράφηκαν). Έτσι μπορούμε να μετρήσουμε όλους τους πρώτους αριθμούς μεγαλύτερους του \(i\) που υπάρχουν στο \(Y\).
Αν μπω μια φορά εδώ σταματάω το loop μου αφού τώρα \(Χ = Y\).
Case \(3\): \(a < b\)
Αναγκαστηκά πρέπει να φύγουμε όλες τις εμφανίσεις των πρώτων διαιρετών του \(Χ\) που είναι \(> i\) για να πολλαπλασιάσουμε το \(Χ\) με \(b - a\) φορές το \(i\). Όταν τους διαγράψουμε διαιρώντας το \(Χ\) με αυτούς θα ισχύει (παρόμοια με το Case \(2\)) θα έχουμε όλους τους πρώτους \(\le i\) στο \(Χ\) ίσες φορές με το \(Y\) (\(a = b\) για όλους τους πρώτους \(\le i\)) και δεν έχουμε άλλους πρώτους στο \(X\) (αφού διαγράφηκαν). Έτσι μπορούμε να μετρήσουμε όλους τους πρώτους αριθμούς μεγαλύτερους του \(i\) που υπάρχουν στο \(Y\).
Αν μπω μια φορά εδώ σταματάω το loop μου αφού τώρα \(Χ = Y\).
Τώρα μας μένει να βρούμε τα \(i\) και για κάθε \(i\) να βρούμε το \(a\) και το \(b\).
Ο πιο απλός τρόπος είναι αυτός:
set<int>primes //εδώ θα αποθυκεύσουμε όλα τα i
map<int,int>a,b; //εδώ θα αποθυκεύω τα a και b
for(int i = 2;i * i <= X;i++){
if(X % i == 0){
primes.insert(i);
while(X % i == 0){
X /= i;
a[i]++;
}
}
}
///Μην ξεχάσετε την περίπτωση που το X δεν έγινε 1
if(X != 1){
primes.insert(X);
a[X]++;
}
for(int i = 2;i * i <= Y;i++){
if(Y % i == 0){
primes.insert(i);
while(Y % i == 0){
Y /= i;
b[i]++;
}
}
}
if(Y != 1){
primes.insert(Y);
b[Y]++;
}
for(auto i:primes){
///και κάνουμε τις περιπτώσεις
}
Subtask 3 (100 points)
\(1 \le Q \le 10^6\)
\(1 \le X,Y \le 4\cdot10^6\)
To μόνο που θα αλλάξει εδώ θα είναι το τελευταίο κομμάτι. Μπορούμε να κάνουμε μια ποιο advance τεχνική για να βρούμε τον μεγαλύτερο πρώτο διαιρέτη κάθε αριθμού με precalculation.
Αυτό η τεχνική λέγεται sieve of eratosthenes:
int maxprime[MAXN+5] = {0};
maxprime[1] = 1;
for(int i = 2;i <= MAXN;i++){
if(maxprime[i] == 0){ // εδώ αυτό σημαίνει ότι το i είναι πρώτος
for(int j = i;j <= MAXN, j += i){
maxprime[j] = i;
}
}
}
Σημείωση
Γενικά είναι καλό να γνωρίζετε πως \(Ν + Ν/2 + Ν/3 + .... + Ν/Ν\) είναι ίσο περίπου με \(Ν log N\).
int a[MAXN] = {0},b[MAXN] = {0}; //εδώ θα αποθυκεύω τα a και b στο τέλος του κάθε query πρέπει να τα ξαναμηδενίζω αλλά χωρίς να περάσω από άσκοπες θέσεις
set<int>primes //εδώ θα αποθυκεύσουμε όλα τα i
while(X != 1){
primes.insert(maxprime[X]);
a[maxprime[X]]++;
X /= maxprime[X];
}
while(Y != 1){
primes.insert(maxprime[Y]);
b[maxprime[Y]]++;
Y /= maxprime[Y];
}
for(auto i:primes){
///και κάνουμε τις περιπτώσεις
}
///Μηδενίζω το a και το b για να είναι έτοιμα για τα επόμενα queries
for(auto i:primes){
a[i] = b[i] = 0;
}