模拟，开始时以为要注意去重，当输出时，判断与前一个是否重复，后来发现没这必要，如果重复了，那后边那组肯定不是互质的

analysis里给出了“super fast solution"的方法，类似杨辉三角，想起了高中时的阿炳老师--两个肩上数之和～～

 

1 /* ID:linyvxi1  2    PROB:frac1  3    LANG:C++  4 */  5 #include 
     
        6 #include 
      
         7 using namespace std;  8 typedef struct Frac{
    9     int up; 10     int down; 11 }Frac; 12 Frac frac[100000]; 13 int total_solutions=1; 14 bool cmp(Frac a,Frac b) 15 {
   16     return ((float)a.up/a.down)<((float)b.up/b.down); 17 } 18 int gcd(int a,int b) 19 {
   20     int temp; 21     while(b){
   22         temp=a%b; 23         a=b; 24         b=temp; 25     } 26     return a; 27 } 28 void trans(int n) 29 {
   30     int i; 31     for(i=1;i