25547 신기한 숫자 (백준, python3)

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

시간 제한	메모리 제한
1초	1024MB

문제

두 양의 정수 A, B가 주어질 때, 다음과 같은 조건을 만족하는 양의 정수 C의 개수를 구하여라.

 

GCD(A, B) = GCD(A, C), LCM(A, B) = LCM(B, C)

 

GCD(A, B)는 A와 B의 최대공약수를, LCM(A, B)는 A와 B의 최소공배수를 의미한다.

 

입력

양의 정수 A, B가 주어진다. (1 ≤ A, B ≤ 1,000,000,000)

 

출력

조건을 만족하는 양의 정수 C의 개수를 출력한다.

 

---

풀이

매우 난해한 문제 같지만 주어진 식을 정리해보면 매우 간단한 문제입니다. 먼저 최대공약수 식을 정리해봅시다. GCD(A, B)를 G라고 했을 때, A = a*G, B = b*G로 표현할 수 있습니다. 여기서 a, b는 서로소입니다. GCD(A, C)가 같으므로 C = c*G로 표현할 수 있습니다. 여기서 a와 c는 서로소이지만 b와 c는 서로소가 아닐 수 있습니다. 따라서 B와 C는 서로소가 아닐 가능성을 표현하기 위해 B = b'*k*G, C = c'*k*G로 표현하겠습니다. a와 b'*k는 서로소이며 a와 c'*k는 서로소입니다.

GCD(A, B) = GCD(A, C) = G
A = a * G
B = b * G
C = c * G
(a와 c는 서로소이지만 b와 c는 1이상의 공약수를 가질 수 있음)
GCD(b, c) = k (k는 1이거나 a의 약수가 아닌 정수)
GCD(B, C) = G * k
B = b' * k * G
C = c' * k * G

 

이제 최소공배수를 정리해봅시다. LCM(A, B)는 L로 표현하겠습니다. 최대공약수와 최소공배수의 관계에 따라 다음 식을 도출할 수 있습니다.

LCM(A, B) = LCM(B, C) = L
L = A * B / G = a * G * b * G / G = a * b * G = a * b' * k * G
   = (B * C) / (G * k) = (b' * c' * k * k * G * G) / (G * k) = b' * c' * k * G
a * b' * k * G = b' * c' * k * G
a = c'
C = a * k * G = A * k

a와 c'은 같습니다. a와 b는 입력으로 주어지는 A, B로 곧바로 얻을 수 있으므로 가능한 C의 개수를 파악하기 위해 k의 개수를 파악해야 합니다. k는 b의 약수이므로 C는 k의 약수의 개수와 같습니다. 하지만 조건이 몇 가지 더 필요합니다.

 

위 식에서 C = A * k임이 확인되었습니다. C는 A의 배수이므로 GCD(A, C) = A입니다. GCD(A, B) = GCD(A, C)이므로 B도 A의 배수여야 합니다. 만약 B가 A의 배수가 아닌 경우, C를 만들 수 있는 k는 존재하지 않습니다. 조건을 다음과 같이 정리할 수 있습니다.

 

1. B mod A > 0인 경우, 조건을 만족하는 C는 존재하지 않는다.
2. B mod A = 0인 경우, 조건을 만족하는 C는 B의 약수의 개수만큼 존재한다.

 

 

정답 코드

import sys
input = sys.stdin.readline
def solution():
    a, b = map(int, input().split())
    if b % a:
        print(0)
    else:
        b //= a
        res = 0
        for i in range(1, int(b ** 0.5) + 1):
            if b % i == 0: res += 2
        if int(b ** 0.5) ** 2 == b: res -= 1
        print(res)
solution()