USACO 2.1 - Ordered Fractions

Consider the set of all reduced fractions between 0 and 1 inclusive with denominators less than or equal to N.

Here is the set when N = 5:

0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1

Write a program that, given an integer N between 1 and 160 inclusive, prints the fractions in order of increasing magnitude.

PROGRAM NAME: frac1

INPUT FORMAT

One line with a single integer N.

SAMPLE INPUT (file frac1.in)

5

OUTPUT FORMAT

One fraction per line, sorted in order of magnitude.

SAMPLE OUTPUT (file frac1.out)

0/1
1/5
1/4
1/3
2/5
1/2
3/5
2/3
3/4
4/5
1/1

출처: http://train.usaco.org/

0부터 1사이의 분모가 N보다 작거나 같은 reduced fractions을 모두 출력하시오. 

N이 5일경우 답은  0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1

결과값은 오름차순으로 정렬되어야 됩니다.

reduced fractions 을 구하기 위해 Euclidean algorithm 을 사용해 최대 공약수를 구하고 최대 공약수가 1인 분수를 오름차순으로 출력하기 위해 multimap 을 사용해 풀었습니다.

my solving

c++

#include <fstream>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
 
struct Fraction
{
    int numerator, denominators;
    Fraction(int n, int d) : numerator(n), denominators(d) { };
};
 
//GCD is Greatest common divisor
int calcGCD(int a, int b)
{
    int remainder;
    if (a < 1 || b < 1) 
        return 0;
 
    if (a < b) 
        return calcGCD(b, a);
 
    while ((remainder = a % b) != 0) 
    { 
        a = b; 
        b = remainder; 
    }
    return b;
}
 
 
 
int main()
{
    ifstream fin("frac1.in");
    ofstream fout("frac1.out");
    multimap<double, Fraction> ret;
    int n;
    fin >> n;
    if (n > 0)
        ret.insert(make_pair(0, Fraction(0, 1)));
    for (int denominators = 1; denominators <= n; denominators++)
    {
        for (int numerator = 1; numerator <= denominators; numerator++)
        {
            if (calcGCD(denominators, numerator) == 1)
            {
                ret.insert(make_pair((double)numerator / (double)denominators, Fraction(numerator, denominators)));
            }
        }
    }
 
    for (multimap<double, Fraction>::iterator it = ret.begin(); it != ret.end(); it++)
        fout << it->second.numerator << "/" << it->second.denominators << endl;
    
 
    fin.close();
    fout.close();
    return 0;
}