[BaekJoon] 13412 서로소 쌍

1.  문제 링크

2.  문제

요약

• 서로소인 두 자연수 A,B의 최소공배수 N이 주어질 때, N을 최소공배수로 하는 A,B가 될 수 있는 숫자 쌍의 개수를 구하는 문제입니다.
• 입력: 첫 번째 줄에는 테스트 케이스의 개수가 주어지고 다음 줄부터 테스트 케이스 수만큼 최소공배수 N이 주어집니다.
• 출력: N을 최소공배수로 하는 서로소인 자연수 쌍의 개수를 테스트 케이스 순서대로 한 줄씩 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;

public class Main {
	public int gcd(int a, int b) {
		if(b == 0) {
			return a;
		} else {
			return gcd(b, a % b);
		}
	}
	public int[] getPairNum(int[] testcase) {
		int[] result = new int[testcase.length];
		for(int i = 0; i < testcase.length; i++) {
			HashMap<Integer, Integer> pair = new HashMap<Integer, Integer>();
			for(int j= 1; j <= Math.sqrt(testcase[i]); j++) {
				if(testcase[i] % j == 0) {
					if(pair.containsKey((int)testcase[i] / j)) {
						continue;
					}
					int gcd = gcd(testcase[i] / j, j);
					if(gcd == 1) {
						pair.put(j, testcase[i] / j);
					}
				}
			}
			result[i] = pair.size();
		}
		return result;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int num = Integer.parseInt(br.readLine());
		int[] testcase = new int[num];
		for(int i = 0; i < testcase.length; i++) {
			testcase[i] = Integer.parseInt(br.readLine());
		}
		br.close();
		Main m = new Main();
		int[] result = m.getPairNum(testcase);
		for(int i = 0; i < result.length; i++) {
			bw.write(result[i] + "\n");
		}
		bw.flush();
		bw.close();
	}
}

4.  접근

• 두 자연수가 서로소이기 때문에 서로소이면서 두 자연수를 곱했을 때 N이 되는 자연수 쌍들을 찾아 개수를 구하면 되는 문제입니다.
• 두 자연수를 곱했을 때 N이 되는 자연수 쌍을 찾으면 되므로 N의 제곱근까지만 확인을 하면 됩니다.
• N의 제곱근을 넘어선 수들은 N의 제곱근보다 작은 수들과 쌍을 이루기 때문에 N의 제곱근을 초과하는 수는 확인하지 않아도 됩니다.
• 이렇게 구한 두 수가 서로소인지 확인하기 위해 두 수의 최대공약수가 1인지 확인하고 만약 서로소가 맞다면 이를 HashMap에 넣습니다.
• 모든 수들의 쌍을 다 확인했다면 HashMap의 크기가 가능한 두 자연수 쌍의 개수가 되므로 HashMap의 크기를 출력합니다.