题目大意:
输入一个自然数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