黑客演习超过时限

Question

我正在试图解决本练习 in HackerEarth。但我有一个错误的时限超过了。这就是我写的代码：

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

class TestClass {
    //gcd 
    public static long gcd(long num1, long num2) {
        if (num2 != 0) {
            return gcd(num2, num1 % num2);
        } else {
            return num1;
        }
    }

    public static void main(String args[] ) throws Exception {
        //BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine()); // Reading input from STDIN
        while (T-- > 0) {
            StringTokenizer st1 = new StringTokenizer(br.readLine());
            long a = Long.parseLong(st1.nextToken());
            long b = Long.parseLong(st1.nextToken());
            long A = a/gcd(a,b);
            long B = b/gcd(a,b);
            System.out.printf("%d%1s%d%n",B,"",A);
        }
    }
}

Answer 1

您的解决方案有点慢，因为实现不好。我用您的解决方案的相同逻辑和时间复杂度在更好的实现中重写了您的解决方案，并被接受，并且没有一个测试用例超过.8第二。

import java.util.*;
 
class TestClass {
    // Same gcd function but it's better code :)
    public static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);   
    }
 
    public static void main(String args[] ) throws Exception {
        Scanner s = new Scanner(System.in);
        int t = s.nextInt();  // this way of reading input is faster alot.
        while(t-- > 0) {
            int a = s.nextInt();  
            int b = s.nextInt();  // No need to use long it's  just 1e9

            int tmp = gcd(a, b);  // It's better to save the value of the gcd(a, b) instead of calculate it twice. 

            int A = a/tmp;
            int B = b/tmp;
            System.out.println(B+" "+A);
        }
    }
}