一道PAT1062 最简分数 测试用例运行超时

测试积点老人

[color=rgba(0, 0, 0, 0.75)]我的思路是：先通分，这里通分是把三个分母全部乘起来，然后会有一个分子的上界和下界。例如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。在确定了上下界后，只要循环一次，看一下哪些是最简分数，输出即可
[color=rgba(0, 0, 0, 0.75)]代码如下：

1. 
   
2. import java.io.*;
   
3. public class Main {
   
4.     private int num1;
   
5. 
   
6.     public Main(int num1){
   
7.         this.num1=num1;
   
8.     }
   
9. 
   
10.     private boolean hasGCD(int num2){//求是否有除了1之外的公约数的方法
    
11.         while(num1!=num2){
    
12.             if(num1>num2) num1=num1-num2;
    
13.             else num2=num2-num1;
    
14.         }
    
15.         if(num1!=1) return true;
    
16.         else return false;
    
17.     }
    
18. 
    
19.     public static void main(String[] args) throws IOException {
    
20.         BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    
21. 
    
22.         String[] num=br.readLine().split(" ");
    
23.         String[] N1M1=num[0].split("/");
    
24.         String[] N2M2=num[1].split("/");
    
25. 
    
26.         int N1=Integer.parseInt(N1M1[0]),M1=Integer.parseInt(N1M1[1]);
    
27.         int N2=Integer.parseInt(N2M2[0]),M2=Integer.parseInt(N2M2[1]);
    
28.         int K=Integer.parseInt(num[2]);
    
29. 
    
30.         int min=N1*M2*K,max=N2*M1*K;//通分后分子的最小值最大值
    
31.         int minK=min/(M1*M2)+1,maxK=max/(M1*M2);//约分后分子的最小值最大值
    
32. 
    
33.         int temp;
    
34.         if(minK>maxK){
    
35.             temp=maxK;
    
36.             maxK=minK;
    
37.             minK=temp;
    
38.         }//这一段是为了防止前一个分数比后面一个分数大的情况，刁钻的测试用例
    
39. 
    
40.         String result="";
    
41.         for(int i=minK;i<=maxK;i++){
    
42.             if(!new Main(i).hasGCD(K)) result+=i+"/"+K+" ";//没有公约数就拼接上去，最后打印再去尾部空格
    
43.         }
    
44. 
    
45.         System.out.print(result.trim());
    
46.     }
    
47. }

复制代码

这段代码进去测试点2运行超时了，具体问题在哪里？

kallinr

qqq911

下个断点看看

郭小贱

这个只能让懂Java代码的同学帮着看看了...

jingzizx

先看结果是啥啊