[백준 13412] 서로소 쌍 (C++)

https://www.acmicpc.net/problem/13412

문제

---

두 자연수 A, B의 최대공약수를 GCD(A, B)라고 할 때, A와 B가 서로소면 GCD(A, B) = 1이다. 두 자연수 A, B의 최소공배수를 LCM(A, B)라고 할 때, A와 B가 서로소면 LCM(A, B) = A x B이다.

어떤 자연수 N이 서로소인 두 자연수 A, B의 최소공배수라고 할 때, A, B로 가능한 숫자 쌍은 여러 개가 있을 수 있다. 예를 들어 N = 30인 경우 30을 최소공배수로 하는 서로소인 두 자연수로 가능한 숫자 쌍은 (1, 30), (2, 15), (3, 10), (5, 6)의 4가지가 있다.

자연수 N이 주어질 때 N을 최소공배수로 하는 서로소인 자연수 쌍의 개수를 출력하는 프로그램을 작성하시오.

 

입력

---

첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 다음 줄부터 차례로 T개의 테스트 케이스가 주어진다. 각각의 테스트 케이스의 첫째 줄에 100,000,000이하의 자연수 N이 주어진다.

 

출력

---

각 테스트 케이스의 답을 순서대로 출력한다. 각 테스트 케이스마다 첫 줄에 N을 최소공배수로 하는 서로소인 자연수 쌍의 개수를 한 줄에 하나씩 출력한다.

 

문제 풀이

---

수학 문제.

 

A와 B가 서로소이면 LCM(A, B) = A x B이므로, A와 B는 둘 다 입력받는 N의 약수가 된다. 1부터 루트N까지 확인하며 N이 해당 수로 나누어 떨어지면 N / A = B도 나누어떨어지게 된다. 유클리드 호제법을 이용하여 A와 B의 최대공약수를 구했을 때 1이 나오면 우리가 찾는 서로소 쌍 중 하나이다.

 

아래는 코드.

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int getGCD(int x, int y)
{
	if (y == 0)
	{
		return x;
	}
	else
	{
		return getGCD(y, x % y);
	}
}

int main()
{
	int T;
	cin >> T;
	for (int t = 0; t < T; t++)
	{
		int N;
		int answer = 0;
		cin >> N;
		for (int i = 1; i <= sqrt(N); i++)
		{
			if (N % i == 0)
			{
				int j = N / i;
				int gcd = getGCD(i, j);
				if (gcd == 1)
				{
					answer++;
				}
			}
		}
		cout << answer << "\n";
	}
	return 0;
}