题目链接：http://acm.swust.edu.cn/problem/801/
Time limit(ms): 1000 Memory limit(kb): 10000
Description
Consider the set of all reduced fractions between 0 and 1 inclusive with denominators less than or equal to N.
Here is the set when N = 5:
0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1
Write a program that, given an integer N between 1 and 160 inclusive, prints the fractions in order of increasing magnitude.
Input
One line with a single integer N.
Output
One fraction per line, sorted in order of magnitude.
Sample Input
| 5 |
Sample Output
|
0/1
1/5
1/4
1/3
2/5
1/2
3/5
2/3
3/4
4/5
1/1
|
题目大意：给定一个数，代表分母的最大值，从小到大，输出所有分母小于N,值小于等于1的所有分数
直接上代码：
#include <iostream>
#include <algorithm>
#include <cstdio>
#define maxn 1000010
using namespace std;
struct node{
int x, y;
bool operator<(const node &tmp)const{
if (x != tmp.x)
return x*tmp.y < y*tmp.x;
return y > tmp.y;
}
}a[maxn];
int gcd(int a, int b){
return !b ? a : gcd(b, a%b);
}
int main(){
int n, i, j;
while (~scanf("%d", &n)){
int pos = ;
//i代表分母,j代表分子
for (i = ; i <= n; i++){
for (j = ; j <= i; j++){
if (!j&&i != ) continue;
if (gcd(j, i) == ){
a[pos].x = j;
a[pos++].y = i;// x/y
}
}
}
sort(a, a + pos);
for (i = ; i < pos; i++)
printf("%d/%d\n", a[i].x, a[i].y);
}
return ;
}