Integer Fraction Reduction Algorithm - Explanation of the Solution?

Question

This is a continuation of this problem:

Reduction of integer algorithms

The following is a solution to the grandmaster’s problem:

#include <cstdio> #include <algorithm> #include <functional> 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<int>& a, vector<int>& x) { a.resize(n); vector<int>(MAXP, 0).swap(x); for (int i = 0; i < n; ++i) { scanf("%d", &a[i]); for (int j = a[i]; j > 1; j /= p[j]) { ++x[p[j]]; } } } void g(const vector<int>& v, vector<int> 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<int> 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<int> >(z, z.end()), [](int a, int b) { return min(a, b); }); g(a, z); g(b, z); return 0; } 

I don’t understand how it works. Can anyone explain this?

Equivalence is as follows:

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

Answer 1

init simply populates the array P , so P[i] contains the largest simple coefficient i .

f(n,a,x) fills x number of times when the number of f(n,a,x) is divisible by each prime number, counting the powers several times. In fact, computers represent the first factorization of a .

g(v,w) takes a list of numbers v and a simple factorization of w and divides any element of v with a common factor in w, until they share common factors. (Dividing a prime factor means subtracting the power by 1).

So now we have main . First, it initializes the P array and reads in the data lengths (oddly enough, it is never read in the data itself). He then saves simple factorizations of the products of the elements from a and b to x and y, respectively. He then uses the lambda expression in the loop to take the element of the wise minimum of these two factorizations, giving the factorization of the greatest common factor. Finally, he shares the elements in a and b with this common factor.

Answer 2

It revealed:

p [i] is the highest prime factor i

So the loop:

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

will be repeated once for each prime factor x;

He then uses this to calculate simple factors.

And then using them to divide into the corresponding members of the numerator / denominator.