[BOJ] 25547 - 신기한 숫자

문제

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

링크를 확인해보세요.

www.acmicpc.net

문제 정리

시간 제한	메모리 제한	정답 비율
1 초	1024 MB	32.6%

요약

• 두 정수 A와 B가 주어집니다.
• GCD(A, B) = GCD(A, C)과 LCM(A, B) = LCM(B, C)를 만족하는 정수 C의 개수를 구하시오.

입력 조건

• A, B : 1 ~ 109

출력

조건을 만족하는 양의 정수 C의 개수.

---

문제 풀이

C의 범위가 주어져 있지 않습니다. 이것으로 위 두 조건을 만족하는 C는 A와 B에 의하여 특정 범위로 좁혀질 수 있는 것으로 해석하였습니다.

우선 임의의 정수 A, B, C가 위 조건을 만족한다고 가정하여 C의 범위를 찾아보도록 하겠습니다.

1) GCD 조건 정리

GCD(A, B) = T 이라고 하겠습니다.
그러면 A = Ta, B = Tb, C = Tc 로 표현 할 수 있습니다.
최대 공약수로 T를 뽑아내서 a와 b, a와 c는 서로소 입니다.

2) LCM 조건 정리

LCM(A, B) = A * B / GCD(A, B) 이므로 조건을 대입하면 다음과 같습니다.
A * B / T = B * C / GCD(B, C)
위 식을 대입및 정리하면 다음과 같습니다.
a = Tc / GCD(Tb, Tc) = c / GCD(b, c)
따라서 a * GCD(b, c) = c 가 됩니다.

3) a와 c 서로소 조건 이용

a = 1, GCD(b, c) = c 이라는 결론이 나오게 됩니다.

4) 결론

• a = 1 이므로 A = T 즉, B와 C는 A의 배수이여야 합니다.
• GCD(b, c) = c 이므로 B = Tck, C = Tc 즉, B는 C의 배수이여야 합니다.

최종적으로 정리하면 C는 A ~ B 사이에 존재하는 A의 배수이면서 B의 약수의 개수를 찾는 문제가 됩니다.

풀이 코드

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {

    void solve() throws Exception {
        // 변수 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());

        // b가 a의 배수 아닌 경우 0
        if (b % a != 0) {
            System.out.println(0);
        } else {
            // A = T, B = nT 인 경우 C는 1 ~ n T가 가능.
            // 여기서 위에 찾은 조건의 하여 
            // C = (n의 약수) * T인 경우에만 조건을 만족하므로
            // n의 약수 개수 찾기는 문제로 변형
            int range = b / a;
            int cnt = 0;

            for (int i = 1; i * i <= range; i++) {
                if (range % i == 0) {
                    if (range / i == i) {
                        cnt += 1;
                    } else {
                        cnt += 2;
                    }
                }
            }

            System.out.println(cnt);
        }
    }

    public static void main(String[] args) throws Exception {
        new Main().solve();
    }
}