USACO Section 2.1 Ordered Fractions - 用GCD判合法的簡單搜尋

   這道題的意思是輸入一個N..求出用小于等于N的做分母...真分數能有那些..分子分母必須約分完全...并且按從小到大輸出...

   資料範圍不大...直接搜就可以了~~搜的時候判斷下GCD,,為1才表示是合法的..并且先都存起來~~最後排個序再輸出就好了...

/*  
ID: zzyzzy12  
LANG: C++  
TASK: frac1
*/    
#include<iostream>    
#include<stdio.h>    
#include<string.h>    
#include<math.h>    
#include<algorithm>    
#include<queue>
using namespace std;   
int n,num,i,j;
struct node
{
     int x,y;      
}ans[100001]; 
int gcd(int a,int b)
{
     if (b==0) return a;
     return gcd(b,a%b);   
}
bool cmp(node a,node b)
{
     return a.x*b.y<b.x*a.y;
}
int main()
{
     freopen("frac1.in","r",stdin);
     freopen("frac1.out","w",stdout);  
     scanf("%d",&n);
     num=2; 
     ans[1].x=0; ans[1].y=1;
     ans[2].x=1; ans[2].y=1;
     for (i=2;i<=n;i++)
       for (j=1;j<i;j++)
          if (gcd(i,j)==1)
          { 
               ans[++num].x=j;  ans[num].y=i;               
          }
     sort(ans+1,ans+1+num,cmp);
     for (i=1;i<=num;i++)
         printf("%d/%d\n",ans[i].x,ans[i].y);
     return 0;   
}