Problem 2.1.4 Ordered Fractions

출처: https://train.usaco.org/usacogate

---

문제 설명

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.

입력 양식

One line with a single integer N.

출력

One fraction per line, sorted in order of magnitude. 

입력 예 

5

출력 예

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

---

문제 풀이 내용

받은 N보다 작은 정수들로 정수쌍 ( i, j ) 를 만들고 첫번째 수는 0, 마지막 수는 1/1 로 해서 vector에 저장한다. 이때 두수가 서로 서로소가 아닌 경우는 제외한다. 왜냐하면 1/2 = 2/4 = 3/6 ..이 되지만, 문제에서는 1/2만 출력해야 한다. vector를 정렬하는데, (a, b) vs (c, d)의 크기 비교는 a/b vs c/d => ad/bd vs bc/bd => ad vs bc 로 비교하도록 했다.

프로그램 내용

#define MAX_M 161

/// check co-prime a, b -> gcd(a, b) == 1
int CoPrime(int a, int b);

vector <pair<int, int>> sequence;

int main() {
    sequence.push_back(make_pair(0,1));

	for (int denominator = 1; denominator < M+1 ; ++denominator)
        for (int numerator  = 1; numerator < denominator ; ++numerator)
            if( CoPrime(numerator, denominator) == 1)
                sequence.push_back(make_pair(numerator, denominator));

	sequence.push_back(make_pair(1,1));

    sort(sequence.begin()+1, sequence.end()-1, compare2);

    for (int idx= 0; idx < sequence.size(); ++idx)
        fout << sequence[idx].first << "/" << sequence[idx].second << endl;

 

Chapter 2.  Bigger Challenges