【題解】TIOJ 1234 . 數列問題

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n;
vector <pair<int, int> > v;

int gcd(int x, int y){
    if (y == 0) return x;
    return gcd(y, x%y);
}

bool cmp(pair<int, int> x, pair<int, int> y){
    return (((double)x.first)/x.second) < (((double)y.first)/y.second);
}

int main() {
    cin >> n;
    if (n == 2){
        cout << "1\n1/2\n";
        return 0;
    }
    v.clear();
    for (int i = 2; i <= n; i++){
        v.push_back({1, i});
        for (int j = 2; j < i; j++){
            if (gcd(i, j) > 1) continue;
            v.push_back({j, i});
        }
    }
    sort(v.begin(), v.end(), cmp);
    cout << v.size() << "\n";
    cout << v[n-1].first << "/" << v[n-1].second << "\n";
}