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

Question

我的思路是：先通分，这里通分是把三个分母全部乘起来，然后会有一个分子的上界和下界。例如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[0].split("/");
        String[] N2M2=num[1].split("/");

        int N1=Integer.parseInt(N1M1[0]),M1=Integer.parseInt(N1M1[1]);
        int N2=Integer.parseInt(N2M2[0]),M2=Integer.parseInt(N2M2[1]);
        int K=Integer.parseInt(num[2]);

        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运行超时了，具体问题在哪里？

Answer 1

需要注意的是虽然主程序看起来只有1次循环，但是hasGCD中还嵌套了一个循环，所以速度没有想象中那么快。

1. 如果使用hasGCD使用辗转相除法来求公约数，则可以用求模的方式而非依次相减来减少运算次数。
2. 由于K<=1000，所以完全可以对K进行一次质因数分解先求出K的所有因数，这样对于每一个分子只需要直接判断它对这些因数有无余数即可。