一个分数一般写成两个整数相除的形式：N/M，其中M不为0。最简分数是指分子和分母没有公约数的分数表示形式。

现给定两个不相等的正分数 N₁/M₁ 和 N₂/M₂，要求你按从小到大的顺序列出它们之间分母为K的最简分数。

输入格式：

输入在一行中按N/M的格式给出两个正分数，随后是一个正整数分母K，其间以空格分隔。题目保证给出的所有整数都不超过1000。

输出格式：

在一行中按N/M的格式列出两个给定分数之间分母为K的所有最简分数，按从小到大的顺序，其间以1个空格分隔。行首尾不得有多余空格。题目保证至少有1个输出。

输入样例：

7/18 13/20 12

输出样例：

5/12 7/12 刚开始绕了一大圈，想着是先通分，在一一遍历查找即求M1，M2，K三数的最小公倍数Tn，然后用变量tmp = Tn/K来判断符合条件的数并存入数组中使用qsort输出，结果是超时加测试点3,4错误只得了13分； 后来参考了姑娘的代码后找到了另一种简便思路：两次while循环，第一次loop寻找K的正整数倍刚好大于左端点的那个值记录为cnt；第二次loop则是在cnt/K < N2/M2的范围下 寻找符合题意的数并且输出，实现的方法是利用gcd函数，（如果两个数之间的最大公约数为1的话，则说明两数字组成的分数为最简形式） 两个坑：1.题目没说输入的第一个分数一定比第二个小 　　　　2.找左端点的时候一定不要忽略掉N1/M1本身

1 #include
     
       2 #include
      
        3  4 //int cmp(const void *a, const void *b) 5 //{ 6 //    return *(int *)a - *(int *)b; 7 //} 8  9 int gcd(int a, int b)10 {11     if(b == 0)12         return a;13     else14         return gcd(b,a%b);15 } 16 17 void swap(int *a, int *b)18 {19      *a = *a ^ *b;20      *b = *a ^ *b;21      *a = *a ^ *b;    22 } 23 int main()24 {25     int N1,N2,M1,M2,K;26     scanf("%d/%d %d/%d %d",&N1,&M1,&N2,&M2,&K);27     if(N1*M2 > N2*M1)28     {29         swap(&N1,&N2);30         swap(&M1,&M2);31     }32     int cnt = 1;33     while(N1*K >= cnt*M1)//找出遍历左端点 ，注意等号（1号坑） 34     {35         cnt++;36     }37     38     int flag = 0;//cnt*M1 > K*N1 此条件不用写 39     40     while( cnt*M2 < K*N2)41     {42         if(gcd(cnt,K) == 1)//最小公倍数为1，即可说明a，b两数之间无约数； 43         {44             if(flag)45             {46                 printf(" ");47             }48             else49             {50                 flag = 1;51             }52             printf("%d/%d",cnt,K);53         }54         cnt++;55     }56     57     return 0;58  }