【USACO Training】Section 2.1 Ordered Fractions

題目

【題目描述】

給定 N ，求所有形為ab，且 0<=a,b<=n，gcd(a,b)=1 的分數。将其從小到大輸出。

【資料範圍】 N≤160

Analysis

【分析】直接把全部的都給求出來，排完序輸出就行了…

【代碼】

/*
PROG: frac1
ID: y2007031
LANG: C++
*/

#include <cstdio>
#include <algorithm>
using namespace std;

#define mp(i,j) make_pair(i,j)
#define fs first
#define sc second

const int N=;

int n;
pair<int,int> a[N*N];
int len;

inline int gcd(int i,int j)
{
    for (int r;j;r=i%j,i=j,j=r);
    return i;
}

inline int cmp(pair<int,int> Pa,pair<int,int> Pb)
{
    return (double)Pa.fs/Pa.sc<(double)Pb.fs/Pb.sc;
}

int main(void)
{
    freopen("frac1.in","r",stdin);
    freopen("frac1.out","w",stdout);
    scanf("%d",&n);
    for (int i=;i<=n;i++)
        for (int j=i;j<=n;j++)
            if (gcd(i,j)==) a[++len]=mp(i,j);
    sort(a+,a+len+,cmp);
    for (int i=;i<=len;i++) printf("%d/%d\n",a[i].fs,a[i].sc);
    return ;
}