原题链接 一个分数一般写成两个整数相除的形式：N/M，其中M不为0。最简分数是指分子和分母没有公约数的分数表示形式。
现给定两个不相等的正分数 N1/M1 和 N2/M2，要求你按从小到大的顺序列出它们之间分母为K的最简分数。
输入格式：
输入在一行中按N/M的格式给出两个正分数，随后是一个正整数分母K，其间以空格分隔。题目保证给出的所有整数都不超过1000。
输出格式：
在一行中按N/M的格式列出两个给定分数之间分母为K的所有最简分数，按从小到大的顺序，其间以1个空格分隔。行首尾不得有多余空格。题目保证至少有1个输出。
输入样例： 7/18 13/20 12 输出样例： 5/12 7/12注意：
题目没说输入的两个分数一定是第一个小，所以要注意事先判断一下AC的解题思路，如果找一个比5/6大的分数，并且规定分母为k，就分子num就应该大于5*k/6，找比5/6小的分数同理利用这个分子num求解，n1*k小于m1*num && m2*num小于n2*k求最简分数 利用分子分母公约数==1判断代码：
#include <iostream> #include <cstdio> #include <vector> using namespace std; int gcd(int a, int b){ int Max = a>b ? a : b; int Min = a>b ? b : a; int rem = Max%Min;//余数 while(rem!=0){ Max = Min; Min = rem; rem = Max%Min; } return Min; } int main() { int n1, m1, n2, m2,k; scanf("%d/%d %d/%d %d", &n1, &m1, &n2, &m2, &k); if(n1*m2 > n2*m1) { //若输入的两个分数左边比右边大，则交换位置 swap(n1, n2); swap(m1, m2); } bool flag = true; int num = n1*k/m1 + 1; //因为不可能是原来的分数，除尽或者除不尽都要+1 while(n1*k<m1*num && m2*num<n2*k){//对应分子比较 从num开始遍历看是不是最简 if(gcd(num, k) == 1) { if(!flag) printf(" "); printf("%d/%d", num, k); flag = false; } num++; } return 0; } 下面贴一下之前的错误代码，代码1第三个样例超时，代码2第三个样例结果错误思路是先通分，分子从小到大遍历，筛选符合输出 错误代码1： #include <iostream> #include <cstdio> #include <vector> using namespace std; int gcd(int a, int b){ int Max = a>b ? a : b; int Min = a>b ? b : a; int rem = Max%Min;//余数 while(rem!=0){ Max = Min; Min = rem; rem = Max%Min; } return Min; } int main() { int n1, m1, n2, m2,k; scanf("%d/%d %d/%d %d", &n1, &m1, &n2, &m2, &k); int t1 = gcd(n1, m1); int t2 = gcd(n2, m2); n1 /= t1; m1 /= t1; n2 /= t2; m2 /= t2; int Max = (n1*m2*k)>(n2*m1*k) ? n1*m2*k : n2*m1*k; int Min = (n1*m2*k)<(n2*m1*k) ? n1*m2*k : n2*m1*k; bool flag = true; for(int i=Min+1; i<Max; i++){ if(i%(m1*m2) != 0) continue; int t = i/(m1*m2); if(gcd(t,k) == 1){ if(!flag) printf(" "); printf("%d/%d", t, k); flag = false; } } return 0; }错误代码2：
#include <iostream> #include <cstdio> #include <vector> using namespace std; int gcd(int a, int b){ int Max = a>b ? a : b; int Min = a>b ? b : a; int rem = Max%Min;//余数 while(rem!=0){ Max = Min; Min = rem; rem = Max%Min; } return Min; } int help(int a, int b, int c){ int Max = a>b ? a : b; Max = Max>c ? Max : c; for(int i=Max; i<a*b*c; i++){ if(i%a==0 && i%b==0 && i%c==0) return i; } return a*b*c; } int main() { int n1, m1, n2, m2,k; scanf("%d/%d %d/%d %d", &n1, &m1, &n2, &m2, &k); int t1 = gcd(n1, m1); int t2 = gcd(n2, m2); n1 /= t1; m1 /= t1; n2 /= t2; m2 /= t2; int A = help(m1, m2, k);//最小公倍数 int Max = n1*(A/m1)>n2*(A/m2) ? n1*(A/m1) : n2*(A/m2); int Min = n1*(A/m1)<n2*(A/m2) ? n1*(A/m1) : n2*(A/m2); bool flag = true; int x = A/k; for(int i=Min+1; i<Max; i++){ if(i%x != 0) continue; int t = i/x; if(gcd(t,k) == 1){ if(!flag) printf(" "); printf("%d/%d", t, k); flag = false; } } return 0; }