[백준] 13412번 서로소 쌍(c) 문제풀이

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

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을 최소공배수로 하는 서로소인 자연수 쌍의 개수를 한 줄에 하나씩 출력한다.

예제 입력)

3
30
16
60060

예제 출력)

4
1
32

<아이디어>

이 문제는 유클리드 호제법을 사용하는 문제이다. 유클리드 호제법에 대해 제대로 모르고 있다면 https://justicehui.github.io/easy-algorithm/2018/08/11/GCD/

[수학알고리즘] 유클리드 호제법

justicehui님의 블로그를 통해 이해하는 것을 추천한다!

 

문제를 풀어보기 전에 이 점을 확실히 짚고 넘어가보자...

일단 입력받은 수 a를 최소공배수로 가지는 수를 x,y라고 해보자.

a가 x의 배수이기 때문에 자연스럽게 x는 a의 약수일 것이다.

그렇다면 a를 x로 나눈 나머지가 0이므로 a%x==0이 될 것이다.(y의 경우도 동일하다.)

 

이 점을 명심하고 문제를 풀어보잣

 

우리는 문제 조건에 따라 a를 최소공배수로 하는 서로소인 자연수 쌍의 개수를 구해야 한다.

어떤 자연수 i와 j가 있다고 했을 때 i와 j가 a를 최소공배수로 하는 서로소인 자연수 쌍이 되려면

i*j==a이어야 하고 gcd(i,j)==1을 만족해야 한다.

이때 j를 i에 대해 정리해보면

i*j==a를 만족해야 하므로 j=a/i라고 할 수 있다. 이를 통해 다시 위에서 말했던 문장을 정리해서 나타내보면,,

a%i==0을 만족하면서 gcd(i,a/i)==1을 만족하는 경우의 개수가 우리가 찾아야 하는 값이라는 것이다.

 

이것이 이 문제를 풀기 위한 핵심 아이디어라고 생각했고

다음과 같은 내용을 소스코드로 나타내면 다음과 같다.

<소스코드>

#include <iostream>
using namespace std;

int gcd(int a,int b)//유클리드 호제법
{
    if(b==0)return a;
    return gcd(b,a%b);
}
int T; //테스트케이스의 개수
int a; //최소공배수

int main()
{
    scanf("%d",&T);
    while(T--) //T번 실행
    {
        scanf("%d",&a);
        int ans=1; //서로소인 자연수 쌍의 개수
//어떤 자연수이던 (1,a)는 반드시 서로소인 자연수 쌍에 포함되기 때문에 1로 초기화

        for(int i=2;i*i<=a;i++) //ans를 1로 초기화한 것과 같은 이유로 i=2부터 시작
//예를 들어 a를 30이라 했을 때 서로소인 자연수 쌍이(2,15)와 (15,2) 두 가지 경우가 들어가면
//안 되기 때문에 i*i<=a가 될 때까지만 반복
        {
                if(a%i==0)
                {
                    if(gcd(i,a/i)==1)ans++;
                } //a%i가 0이고 gcd(i,a/i)가 1이라면 ans에 1을 더한다.
        }
        printf("%d\n",ans);
    }
    return 0;
}