1076.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1076 on 2006-01-09 at 13:04:03 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int LIMIT = 160;
const int MAX = 8000;

class Fraction {
public:
	int n, d;
	bool operator <(const Fraction&) const;
	void set(int, int);
};
bool Fraction::operator <(const Fraction& f) const {
	return (n * f.d < f.n * d);
}
void Fraction::set(int ni, int di) {
	n = ni, d = di;
}

int gcd(int, int);

int main()
{
	Fraction f[MAX] = { { 0, 1 }, { 1, 1 } };
	int i, j, fn = 2;
	int n;
	
	for(i = 2; i <= LIMIT; i++) {
		for(j = 1; j < i; j++) {
			if(gcd(i, j) == 1) f[fn++].set(j, i);
		}
	}
	sort(f, f+fn);
	while(scanf("%d", &n) != EOF) {
		for(i = 0; i < fn; i++) {
			if(f[i].d <= n) printf("%d/%d\n", f[i].n, f[i].d);
		}
		putchar('\n');
	}
	
	return 0;
}

int gcd(int a, int b)
{
	if(a % b == 0) return b;
	else return gcd(b, a%b);
}