[백준 13412] 서로소 쌍

 

문제에서 서술해준 대로 GCD = 1, LCM = A*B 인 경우를 찾아서 카운트한다.

 

N = 30 일때 완전탐색으로 

(1, 30), (2, 15), (3, 10), (5, 6), (6, 5), (10, 3), (15, 2), (30, 1) 을 찾을 수 있다.

총 개수/2 를 하게되면 N이 큰 수 일때 TLE 가 발생한다.

 

(5, 6) => (6, 5) 로 넘어갈때 오른쪽수보다 왼쪽수가 더 커지게 된다.

이 부분을 체크하여 시간초과를 해결해 주었다.

 

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int t = sc.nextInt();
        while(t-->0) {
            int n = sc.nextInt();
            int cnt = 0;
            int min = Integer.MAX_VALUE;
            for(int i=1; i<=n; i++) {
                if(n%i == 0) {
                    int x = i;
                    int y = n/i;
                    if(x >= min) break;
                    min = Math.min(min, y);
                    int g = gcd(x, y);
                    int l = lcm(x, y);
                    if(g == 1 && l == x*y) cnt++;
                }
            }
            System.out.println(cnt);
        }
    }
    
    public static int gcd(int x, int y) {
        while(y != 0) {
            int temp = y;
            y = x % y;
            x = temp;
        }
        return x;
    }
    
    public static int lcm(int x, int y) {
        return x * y / gcd(x, y);
    }
}