一道PAT1062 最简分数 测试用例运行超时
我的思路是：先通分，这里通分是把三个分母全部乘起来，然后会有一个分子的上界和下界。例如7/18 13/20 12 通分后有7/18=1680/4320 13/20=2808/4320 而对于任意的正整数x，都有x/12=360*x/4320。那么这个360x就要在1680和2808之间。那么x的最小值就是1680/360+1=5 最大值就是2808/360=7。在确定了上下界后，只要循环一次，看一下哪些是最简分数，输出即可
代码如下：
import java.io.*;
public class Main {
private int num1;
public Main(int num1){
this.num1=num1;
}
private boolean hasGCD(int num2){//求是否有除了1之外的公约数的方法
while(num1!=num2){
if(num1>num2) num1=num1-num2;
else num2=num2-num1;
}
if(num1!=1) return true;
else return false;
}
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String[] num=br.readLine().split(" ");
String[] N1M1=num.split("/");
String[] N2M2=num.split("/");
int N1=Integer.parseInt(N1M1),M1=Integer.parseInt(N1M1);
int N2=Integer.parseInt(N2M2),M2=Integer.parseInt(N2M2);
int K=Integer.parseInt(num);
int min=N1*M2*K,max=N2*M1*K;//通分后分子的最小值最大值
int minK=min/(M1*M2)+1,maxK=max/(M1*M2);//约分后分子的最小值最大值
int temp;
if(minK>maxK){
temp=maxK;
maxK=minK;
minK=temp;
}//这一段是为了防止前一个分数比后面一个分数大的情况，刁钻的测试用例
String result="";
for(int i=minK;i<=maxK;i++){
if(!new Main(i).hasGCD(K)) result+=i+"/"+K+" ";//没有公约数就拼接上去，最后打印再去尾部空格
}
System.out.print(result.trim());
}
}这段代码进去测试点2运行超时了，具体问题在哪里？
:time: 下个断点看看 这个只能让懂Java代码的同学帮着看看了... 先看结果是啥啊
页:
[1]
