[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	

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注