USACO 2.1 Ordered Fractions

Ordered Fractions

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.

PROGRAM NAME: frac1

INPUT FORMAT

One line with a single integer N.

SAMPLE INPUT (file frac1.in)

OUTPUT FORMAT

One fraction per line, sorted in order of magnitude.

SAMPLE OUTPUT (file frac1.out)

0/1

1/5

1/4

1/3

2/5

1/2

3/5

2/3

3/4

4/5

1/1

题目大意：就是说给定一个N，输出值在0到1之间的，分母在1到N之间的所有值不重复的分数（可以约分的需要约分）。

思路：很简单，因为数据量小，所以就是枚举分子分母，然后不要不是最简分数的分数，再排序。

 /*

 ID:fffgrdc1

 PROB:frac1

 LANG:C++

 */

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 int prime[],primecnt=;

 bool bo[]={};

 struct str

 {

     int x;int y;

     double ans;

 }e[];

 bool kong(str aa,str bb)

 {

     return aa.ans<bb.ans;

 }

 bool check(int x,int y)

 {

     //int temp=sqrt(double (y));

     for(int i=;i<=primecnt&&prime[i]<=y;i++)

     {

         if(!(y%prime[i]))

             if(!(x%prime[i]))

                 return ;

     }

     return ;

 }

 int main()

 {

     freopen("frac1.in","r",stdin);

     freopen("frac1.out","w",stdout);

     int n;

     scanf("%d",&n);

     int anscnt=;

     bo[]=bo[]=;

     for(int i=;i<;i++)

     {

         if(!bo[i])

         {

             prime[++primecnt]=i;

             for(int j=;j*i<;j++)

             {

                 bo[i*j]=;

             }

         }

     }

     for(int i=;i<=n;i++)

     {

         for(int j=;j<i;j++)

         {

             if(check(j,i))

             {

                 e[++anscnt].x=j;

                 e[anscnt].y=i;

                 e[anscnt].ans=(j*1.0)/i;

             }

         }

     }

     sort(e+,e++anscnt,kong);

     printf("0/1\n");

     for(int i=;i<=anscnt;i++)

     {

         printf("%d/%d\n",e[i].x,e[i].y);

     }

     printf("1/1\n");

     return ;

 }

check函数写的太烂了。。。WA了几发都是因为想优化它。本来是想到用GCD的，但是担心时间复杂度的问题，后来学长告诉我不用担心呀，而且甚至不用自己手写，algorithm里面有现成的。。。于是代码变成下面这样也A了，而且复杂度下降了。。。。惊了

 /*

 ID:fffgrdc1

 PROB:frac1

 LANG:C++

 */

 #include<cstdio>

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 int prime[],primecnt=;

 bool bo[]={};

 struct str

 {

     int x;int y;

     double ans;

 }e[];

 bool kong(str aa,str bb)

 {

     return aa.ans<bb.ans;

 }

 bool check(int x,int y)

 {

     return __gcd(x,y)==;

 }

 int main()

 {

     freopen("frac1.in","r",stdin);

     freopen("frac1.out","w",stdout);

     int n;

     scanf("%d",&n);

     int anscnt=;

     bo[]=bo[]=;

     for(int i=;i<;i++)

     {

         if(!bo[i])

         {

             prime[++primecnt]=i;

             for(int j=;j*i<;j++)

             {

                 bo[i*j]=;

             }

         }

     }

     for(int i=;i<=n;i++)

     {

         for(int j=;j<i;j++)

         {

             if(check(j,i))

             {

                 e[++anscnt].x=j;

                 e[anscnt].y=i;

                 e[anscnt].ans=(j*1.0)/i;

             }

         }

     }

     sort(e+,e++anscnt,kong);

     printf("0/1\n");

     for(int i=;i<=anscnt;i++)

     {

         printf("%d/%d\n",e[i].x,e[i].y);

     }

     printf("1/1\n");

     return ;

 }

巴特西