[USACO][Section 2.1][枚举] Ordered Fractions

题目大意：

输入一个自然数N，对于一个最简分数a/b（分子和分母互质的分数），满足1<=b<=N，0<=a/b<=1，找出所有满足条件的分数。

思路：

利用两层循环进行枚举分子分母，当分子分母最大公约数为1时记录下来。

代码：

/*
ID: lujunda1
LANG: C++
PROG: frac1
*/
#include
#include
using namespace std;
#define datasize (130+1)*130/2
struct point
//利用结构体对分数的分子分母进行封装。 
{
    int a;
    int b;
}arry[datasize];
int gcd(int y,int x)
//求最大公约数。 
{
    return y%x?gcd(x,y%x):x;
}
int cmp(const void* m,const void* n)
//比较函数，对point类型的分数进行大小比较。 
{
    double a=double((*(point*)m).a)/double((*(point*)m).b);
    double b=double((*(point*)n).a)/double((*(point*)n).b);
    if(a>b)
        return 1;
    if(a==b)
        return 0;
    if(a<b)
        return -1;
}
int main()
{
    freopen("frac1.in","r",stdin);
    freopen("frac1.out","w",stdout);
    int n;
    while(~scanf("%d",&n))
    {
        int total=0;
        //total表示除0/1和1/1外最简分数的数量。 
        for(int i=1;i<=n;i++)
            for(int j=1;j<i;j++)
                if(gcd(i,j)==1)
                //最大公约数等于1时，说明分子分母互质。 
                {
                    arry[total].a=j;
                    arry[total++].b=i;
                }
        qsort(arry,total,sizeof(arry[0]),cmp);
        //排序 
        printf("0/1\n");
        for(int i=0;i<total;i++)
            printf("%d/%d\n",arry[i].a,arry[i].b);
        printf("1/1\n");
    }
}