Algorithme de réduction des fractions entières – Explication de la solution?

Ceci est une suite à ce problème:

Algorithme de réduction des fractions entières

Voici une solution au problème d’un grand maître:

#include  #include  #include  using namespace std; const int MAXN = 100100; const int MAXP = 10001000; int p[MAXP]; void init() { for (int i = 2; i < MAXP; ++i) { if (p[i] == 0) { for (int j = i; j < MAXP; j += i) { p[j] = i; } } } } void f(int n, vector& a, vector& x) { a.resize(n); vector(MAXP, 0).swap(x); for (int i = 0; i  1; j /= p[j]) { ++x[p[j]]; } } } void g(const vector& v, vector w) { for (int i: v) { for (int j = i; j > 1; j /= p[j]) { if (w[p[j]] > 0) { --w[p[j]]; i /= p[j]; } } printf("%d ", i); } puts(""); } int main() { int n, m; vector a, b, x, y, z; init(); scanf("%d%d", &n, &m); f(n, a, x); f(m, b, y); printf("%d %d\n", n, m); transform(x.begin(), x.end(), y.begin(), insert_iterator<vector >(z, z.end()), [](int a, int b) { return min(a, b); }); g(a, z); g(b, z); return 0; } 

Ce n’est pas clair pour moi comment ça marche. Quelqu’un peut-il l’expliquer?

L’équivilance est la suivante:

 a is the numerator vector of length n b is the denominator vector of length m 

init remplit simplement le tableau P telle sorte que P[i] contienne le plus grand facteur premier de i .

f(n,a,x) remplit x avec le nombre de fois qu’un nombre en a est divisible par chaque nombre premier, en comptant les puissances plusieurs fois. En fait, il calcule la factorisation première du produit de a .

g(v,w) prend une liste de nombres v et une factorisation première w et divise tout élément de v avec un facteur commun dans w jusqu’à ce qu’ils ne partagent aucun facteur commun. (Diviser la factorisation en nombres premiers signifie soustraire la puissance par 1).

Alors maintenant, nous avons main . D’abord, il initialise le tableau P et lit les longueurs de données (étrangement, il ne semble jamais lire dans les données elles-mêmes). Ensuite, il stocke les factorisations principales des produits d’éléments dans a et b dans x et y respectivement. Ensuite, il utilise une expression lambda dans une boucle pour prendre le minimum élémentaire de ces deux factorisations, donnant la factorisation du plus grand facteur commun. Enfin, il divise les éléments de a et b par ce facteur commun.

Deviner:

p [i] est le facteur premier le plus élevé de i

Donc la boucle:

 for (int i = x; i > 1; i /= p[i]) { p[i] is prime factor of x; } 

itérera une fois pour chaque facteur premier de x;

Il l’utilise ensuite pour compter les facteurs premiers.

Et ensuite, les utiliser pour diviser en termes de numérateur / dénominateur appropriés.