- Identification Rapide des Multiples Dangereux
L'objectif initial consiste à compter combien d'entiers compris dans l'intervalle \([1, N]\) satisfont une condition de dangerosités prédéfinie. Plutôt que de tester chaque nombre individuellement, nous appliquons un principe de marquage direct inspiré du crible d'Ératosthène. Chaque valeur d'entrée sert de pas d'incrémentation pour traverser et taguer systématiquement ses multiples dans un tableau booléen de taille \(N+1\).
Cette approche réduit la complexité globale tout en garantissant qu'aucun multiple ne soit omis. Le parcours final se limite à un simple dénombrement des entrées activées.
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
long long limite_max, nb_independants;
cin >> limite_max >> nb_independants;
vector<long long> valeurs_seminales(nb_independants);
for (size_t idx = 0; idx < nb_independants; ++idx) {
cin >> valeurs_seminales[idx];
}
vector<bool> est_marked(limite_max + 1, false);
for (long long base_val : valeurs_seminales) {
for (long long cur = base_val; cur <= limite_max; cur += base_val) {
est_marked[cur] = true;
}
}
long long resultat_final = 0;
for (long long i = 1; i <= limite_max; ++i) {
if (est_marked[i]) ++resultat_final;
}
cout << resultat_final << '\n';
return 0;
}
- Modélisation Graphique et Calcul de Profondeur sur les Facteurs Premiers
Ce problème impose le calcul de distances entre deux nœuds dans une structure arborescente implicite. La relation de parenté est définie algébriquement : chaque entier \(x\) se connecte à \(x \div \text{pg}(x)\), où \(\text{pg}(x)\) désigne son plus grand facteur premier. Cette règle génère automatiquement un arbre raciné en \(1\).
Une implémenttaion naive construisant explicitement les arêtes et utilisant la levée binaire pour les ancêtres communs (LCA) rencontre des limites temporelles lors de l'initialisation. L'optimisation repose sur un crible linéaire permettant de déterimner simultanément le plus grand facteur premier et la profondeur de chaque nœud. Puisque la hauteur logarithmique de cet arbre reste strictement inférieure à \(24\) pour \(N \le 10^7\), un parcours ascendant direct vers la racine suffit pour résoudre les requêtes, évitant ainsi la surcharge mémoire de la matrice de précalcul.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll borne_sup, nb_interrogations;
cin >> borne_sup >> nb_interrogations;
vector<ll> plus_grand_facteur_premier(borne_sup + 1);
vector<int> profondeur_noeud(borne_sup + 1, 0);
vector<int> liste_premiers;
vector<bool> est_composite(borne_sup + 1, false);
profondeur_noeud[1] = 1;
for (ll i = 2; i <= borne_sup; ++i) {
if (!est_composite[i]) {
liste_premiers.push_back(static_cast<int>(i));
plus_grand_facteur_premier[i] = i;
profondeur_noeud[i] = 2;
}
for (int p : liste_premiers) {
ll produit = i * p;
if (produit > borne_sup) break;
est_composite[produit] = true;
plus_grand_facteur_premier[produit] = max(plus_grand_facteur_premier[i], static_cast<ll>(p));
profondeur_noeud[produit] = profondeur_noeud[produit / plus_grand_facteur_premier[produit]] + 1;
if (i % p == 0) break;
}
}
for (ll q = 0; q < nb_interrogations; ++q) {
ll n1, n2;
cin >> n1 >> n2;
ll chemins_total = profondeur_noeud[n1] + profondeur_noeud[n2];
ll curr1 = n1, curr2 = n2;
while (curr1 != curr2) {
if (profondeur_noeud[curr1] > profondeur_noeud[curr2])
curr1 /= plus_grand_facteur_premier[curr1];
else
curr2 /= plus_grand_facteur_premier[curr2];
chemins_total -= 2;
}
cout << chemins_total << '\n';
}
return 0;
}
- Rationalisation Mathématique et Évaluation en Temps Linéaire
La troisième partie demande le dénombrement des couples \((x, y)\) vérifiant \(1 \le x < y \le n\) et la divisibilité \((y-x) \mid (y+x)\). Une boucle imbriquée exhaustive atteint rapidement une saturation computationnelle. Nous effectuons un changement de variable crucial en posant \(t = y - x\). La condition devient alors \(t \mid (2y - t)\), ce qui équivaut à \(t \mid 2y\).
En fixant \(t\), le nombre de solutions valides pour \(y\) dans l'intervalle \([t+1, n]\) correspond aux multiples de \(t\) contenus dans cet intervalle, soit \(\lfloor \frac{n}{t} \rfloor - 1\). Toutefois, lorsque \(t\) est impair, \(2y\) doit être divisible par \(t\) sans introduire de fraction dans \(y\). Cela impose que les multiples considérés soient pairs, réduisant effectivement la quantité admissible de moitié. La formule finale s'ajuste en soustrayant ces cas invalides :
\[\text{Résultat} = \sum_{t=1}^{n-1} \left( \left\lfloor \frac{2n-t}{t} \right\rfloor - 1 - \delta_{\text{impair}}(t) \cdot \left\lfloor \frac{2n-t}{2t} \right\rfloor \right)\]
#include <iostream>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
long long limite_superieure;
cin >> limite_superieure;
long long paires_valides = 0;
for (long long diff = 1; diff < limite_superieure; ++diff) {
long long compte_brut = (limite_superieure + (limite_superieure - diff)) / diff - 1;
paires_valides += compte_brut;
if (diff % 2 != 0) {
long long retranchement = (limite_superieure + (limite_superieure - diff)) / (2 * diff);
paires_valides -= retranchement;
}
}
cout << paires_valides << '\n';
return 0;
}
- Programmation Dynamique sur legraphe des Diviseurs pour les PPCM
Ici, il faut déterminer, pour chaque entier \(i \in [1, N]\), le nombre de séquences de longueur \(K\) dont le plus petit commun multiple (PPCM) est exactement \(i\), avec des éléments tirés dans \([1, N]\).
Soir \(d(i)\) le nombre de diviseurs de \(i\). Le nombre total de séquences formées uniquement avec les diviseurs de \(i\) vaut \(d(i)^K\). Parmi ces combinaisons, certaines ont un PPCM strictement inférieur à \(i\). En exploitant la relation réciproque sur le treillis des diviseurs, nous pouvons isoler les séquences ayant un PPCM précis :
\[f(i) = d(i)^K - \sum_{\substack{j \mid i \\ j < i}} f(j)\]
Plutôt que d'itérer sur les diviseurs, il est plus efficace de propager la soustraction vers les multiples. En parcourant \(i\) de \(1\) à \(N\) et en retirant \(f(i)\) de tous ses multiples \(j = 2i, 3i, \dots\), nous obtenons une complexité globale de \(O(N \log N)\). Les opérations s'exécutent modulo \(998244353\) pour éviter les débordements.
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
const ll MODULE = 998244353;
ll puissance_modulaire(ll base, ll exposant, ll mod) {
ll residue = 1;
base %= mod;
while (exposant > 0) {
if (exposant & 1) residue = (residue * base) % mod;
base = (base * base) % mod;
exposant >>= 1;
}
return residue;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
long long borne_max, longueur_seq;
cin >> borne_max >> longueur_seq;
vector<ll> nb_diviseurs(borne_max + 1, 0);
for (long long i = 1; i <= borne_max; ++i) {
for (long long j = i; j <= borne_max; j += i) {
nb_diviseurs[j]++;
}
}
vector<ll> combinaison_totale(borne_max + 1);
vector<ll> exact_ppcm(borne_max + 1);
for (long long i = 1; i <= borne_max; ++i) {
combinaison_totale[i] = puissance_modulaire(nb_diviseurs[i], longueur_seq, MODULE);
}
for (long long i = 1; i <= borne_max; ++i) {
exact_ppcm[i] = combinaison_totale[i];
for (long long multiple = i * 2; multiple <= borne_max; multiple += i) {
exact_ppcm[multiple] = (exact_ppcm[multiple] - exact_ppcm[i] % MODULE + MODULE) % MODULE;
}
}
for (long long i = 1; i <= borne_max; ++i) {
cout << exact_ppcm[i] << (i == borne_max ? "" : " ");
}
cout << '\n';
return 0;
}