# Reducing Integer Fractions Algorithm - Solution Explanation?

Filed under:
|
|
|
##### c++11

This is a followup to this problem:

Reducing Integer Fractions Algorithm

Following is a solution to the problem from a grandmaster:

``````#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;
}
``````

It isn't clear to me how it works. Can anyone explain it?

The equivilance is as follows:

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

© Stack Overflow or respective owner

### Related posts about c++

• #### Which C++ book shold I get between "C++ Primer" vs "C++ Primer Plus"

as seen on Stack Overflow - Search for 'Stack Overflow'
I want to learn C++ by using Vim and MinGW as compiler. I'm interesting at "C++ Primer (4th Edition)" and "C++ Primer Plus (5th Edition)" but I don't know how about it different. It has no book store that I can review those books, so I want to know, what is the different between those book and which… >>> More

• #### C++ : C++ Primer (Stanley Lipmann) or The C++ programming language (special edition)

as seen on Stack Overflow - Search for 'Stack Overflow'
I have a Computer Science degree (long2 time ago) .. I do know Java OOP but i am now trying to pick up C++. I do have C and of course data structure using C or pascal. I have started reading Bjarne Stroustrup book (The C++ Programming Language - Special Edition) but find it extremely difficult esp… >>> More

• #### I need help on my C++ assignment using MS Visual C++

as seen on Stack Overflow - Search for 'Stack Overflow'
Ok, so I don't want you to do my homework for me, but I'm a little lost with this final assignment and need all the help I can get. Learning about programming is tough enough, but doing it online is next to impossible for me... Now, to get to the program, I am going to paste what I have so far. This… >>> More

• #### Managed c++ std::string not accessible in unmanaged c++

as seen on Stack Overflow - Search for 'Stack Overflow'
In unmanaged c++ dll i have a function which takes constant std::string as argument Prototype : void read ( const std::string &amp;imageSpec_ ) I call this function from managed c++ dll by passing a std::string. When i debug the unmanaged c++ code the parameter imageSpec_ shows the value correctly… >>> More

• #### The Definitive C++ Book Guide and List

as seen on Stack Overflow - Search for 'Stack Overflow'
After more than a few questions about deciding on C++ books I thought we could make a better community wiki version. Providing QUALITY books and an approximate skill level. Maybe we can add a short blurb/description about each book that you have personally read / benefited from. Feel free to debate… >>> More

### Related posts about algorithm

• #### Jpeg Algorithm vs BMP Algorithm?

as seen on Super User - Search for 'Super User'
I'm just wonder, what the differences are between creating a BMP file algorithm and JPG file algorithm ? If you know the others images' format algorithm, please post them. Thanks. >>> More

• #### word disambiguation algorithm (Lesk algorithm)

as seen on Stack Overflow - Search for 'Stack Overflow'
Hii.. Can anybody help me to find an algorithm in Java code to find synonyms of a search word based on the context and I want to implement the algorithm with WordNet database. For example, "I am running a Java program". From the context, I want to find the synonyms for the word "running", but the… >>> More

• #### Search algorithm (with a sort algorithm already implemented)

as seen on Stack Overflow - Search for 'Stack Overflow'
Hello, Im doing a Java application and Im facing some doubts in which concerns performance. I have a PriorityQueue which guarantees me the element removed is the one with greater priority. That PriorityQueue has instances of class Event (which implements Comparable interface). Each Event is associated… >>> More

• #### Is there any algorithm for finding LINES by PIXEL COLORS on picture?

as seen on Stack Overflow - Search for 'Stack Overflow'
So I have Image like this I want to get something like this (I hevent drawn all lines I want but I hope you can get my idea) I need algorithm for finding all straight lines on it by just reading colors of pixels. No hard math, no Haar, no Hough. Some algorithm which would be based on points… >>> More

• #### collsion issues with quadtree [on hold]

as seen on Game Development - Search for 'Game Development'
So i implemented a Quad tree in Java for my 2D game and everything works fine except for when i run my collision detection algorithm, which checks if a object has hit another object and which side it hit.My problem is 80% of the time the collision algorithm works but sometimes the objects just go… >>> More