1062 最简分数(20)【样例超出范围】_综合

1062 最简分数(20)（20 分）

一个分数一般写成两个整数相除的形式：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

写这道题直接用gcd是很简单的。
__gcd()是agorithm头文件的一个库函数，用于求最大公约数，注意开头有两个短线。
该库函数可计算两个相同的整形变量的最大公约数，不能计算浮点型。
但是一开始我尝试使用类似线性筛的方式，想要将所有约数因子的积标记上，然后不能通过全部样例，~~原因暂且不明~~ ，已解决如下。
我的代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define maxn 1000000007
int ans[1001];
//bool tu[1001];
int main()
{double a,b;int a1,a2,b1,b2,k;scanf("%d/%d %d/%d %d",&a1,&a2,&b1,&b2,&k);a=(double)a1/a2;b=(double)b1/b2;if(a1*b2>a2*b1){swap(a,b);}int cot=0;double te=1.00/k;if(te>a&&te<b) ans[cot++]=1;for(int i=2;i<k;i++){
// if(!tu[i]&&k%i!=0)
// {if((double)i/k>a&&(double)i/k<b&&__gcd(i,k)==1)ans[cot++]=i;
//② else break;
// }
// else if(!tu[i]&&k%i==0)
// {
//① for(int j=i*i;j<k;j+=i)
// {
//# if(j>=k) break;
// tu[j]=1;
// }
// }}for(int i=0;i<cot;i++){printf("%d/%d",ans[i],k);if(i!=cot-1) cout<<' ';}cout<<'\n';
}

原来的代码即将双斜杠和__gcd去掉。

问题已解决，同开始想的一样，最大公约数的排除问题也可以用这个方法来筛选，但是这个代码有问题的地方有两处，上面已标记，第一处要把ii改为i2，这毕竟和合数筛选不一样，如果用i*i还是会有所遗漏，然后是第二处，这个本意是想有些优化，但是实际上是错误的了，应该去除，然后如果修改后直接提交还会在中间的那个测试点发生错误，即使我在//#标记的地方加上这个判断还是会段错误，把tu数组增大了一个单位之后才使得全部测试点都通过，~~原因暂且不明~~ ，已解决，如下。

修改后代码如下：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define maxn 1000000007
int ans[1001];
bool tu[1001];
int main()
{double a,b;int a1,a2,b1,b2,k;scanf("%d/%d %d/%d %d",&a1,&a2,&b1,&b2,&k);
//# if(k>1000) return 0;a=(double)a1/a2;b=(double)b1/b2;if(a1*b2>a2*b1){swap(a,b);}int cot=0;double te=1.00/k;if(te>a&&te<b) ans[cot++]=1;for(int i=2;i<k;i++){if(!tu[i]&&k%i!=0){if((double)i/k>a&&(double)i/k<b)ans[cot++]=i;}else if(!tu[i]&&k%i==0){for(int j=i*2;j<k;j+=i){if(j>=k) break;tu[j]=1;}}}for(int i=0;i<cot;i++){printf("%d/%d",ans[i],k);if(i!=cot-1) cout<<' ';}cout<<'\n';
}

在这里插入图片描述

添加上方**//#**后代码后，结果如上，通不过第三个测试点，即k>1000，故原因是题目所给范围不正确，故导致错误。