25547 신기한 숫자
Table of Contents
접근 방법#
조건으로 주어진 세 수의 최대공약수와 최소공배수의 의미를 파악하여 그에 따라 가능한 $C$의 개수를 세준다.
이를 위해 두 수의 최대공약수와 최소공배수가 어떤 의미를 지니는지 살펴볼 필요가 있다.
두 수의 최대공약수#
두 수의 최대공약수는 두 수를 소인수분해한 꼴을 통해 구할 수 있다.
예를 들어 $12$과 $108$의 최대공약수는 아래과 같이 구할 수 있다.
먼저 $12$를 소인수분해하면,
$$
12 = 2^2 \cdot 3
$$
다음으로 $108$을 소인수분해하면, $$ 108 = 2^2 \cdot 3^3 $$
그런 다음 두 수에서 공통으로 나타나는 소인수 중 지수가 작은 쪽을 채택하면, $$ 2^2 \cdot 3 = 12 $$ 가 두 수의 최대공약수임을 구할 수 있다.
즉, 두 수를 아래와 같이 소인수분해할 수 있다고 할 때, $$ x = p_{1}^{i_1} \cdot p_{2}^{i_2} \cdot p_{3}^{i_3} \cdot … \newline y = p_{1}^{j_1} \cdot p_{2}^{j_2} \cdot p_{3}^{j_3} \cdot … $$ 두 수의 최대공약수는, $$ GCD(x, y) = p_{1}^{min(i_1, j_1)} \cdot p_{2}^{min(i_1, j_2)} \cdot p_{3}^{min(i_3, j_3)} \cdot … $$ 로 구할 수 있다.
두 수의 최소공배수#
두 수의 최소공배수도 두 수를 소인수분해한 꼴을 통해 구할 수 있다.
예를 들어 $12$와 $108$의 최소공배수는 아래과 같이 구할 수 있다.
$$
12 = 2^2 \cdot 3 \newline
108 = 2^2 \cdot 3^3
$$
에서 두 수의 모든 소인수를 채택하고 중복인 소인수는 지수가 큰 쪽을 채택하면,
$$
2^2 \cdot 3^3 = 108
$$
이 두 수의 최소공배수임을 구할 수 있다.
즉, 두 수를 아래와 같이 소인수분해할 수 있다고 할 때, $$ x = p_{1}^{i_1} \cdot p_{2}^{i_2} \cdot p_{3}^{i_3} \cdot … \newline y = p_{1}^{j_1} \cdot p_{2}^{j_2} \cdot p_{3}^{j_3} \cdot … $$ 두 수의 최소공배수는, $$ LCM(x, y) = p_{1}^{max(i_1, j_1)} \cdot p_{2}^{max(i_1, j_2)} \cdot p_{3}^{max(i_3, j_3)} \cdot … $$ 로 구할 수 있다.
$GCD(A, B) = GCD(A, C)$#
위의 내용을 바탕으로 $GCD(A, B)$를 구해보자.
$A$와 $B$를 아래와 같이 소인수분해할 수 있다고 할 때, $$ A = p_{1}^{i_1} \cdot p_{2}^{i_2} \cdot p_{3}^{i_3} \cdot … \newline B = p_{1}^{j_1} \cdot p_{2}^{j_2} \cdot p_{3}^{j_3} \cdot … $$ 두 수의 최대공약수는, $$ GCD(A, B) = p_{1}^{min(i_1, j_1)} \cdot p_{2}^{min(i_1, j_2)} \cdot p_{3}^{min(i_3, j_3)} \cdot … $$ 로 구할 수 있다.
같은 방법으로 $A$와 $C$를 아래와 같이 소인수분해할 수 있다고 할 때, $$ A = p_{1}^{i_1} \cdot p_{2}^{i_2} \cdot p_{3}^{i_3} \cdot … \newline C = p_{1}^{j_1} \cdot p_{2}^{j_2} \cdot p_{3}^{j_3} \cdot … $$ 두 수의 최대공약수는, $$ GCD(A, C) = p_{1}^{min(i_1, j_1)} \cdot p_{2}^{min(i_1, j_2)} \cdot p_{3}^{min(i_3, j_3)} \cdot … $$ 로 구할 수 있다.
그런데 이때 두 최대공약수가 서로 같으려면 $A$와 $C$를 소인수분해할 때 채택된 소인수의 지수 $min(i_k, j_k)$가 $A$와 $B$를 소인수분해할 때 채택된 소인수의 지수와 동일해야 한다.
즉, $GCD(A, B)$의 소인수 $p$에 대해서 그 지수가 $e$라면 $C$는 $p$를 소인수로 $e$개 이상으로 가지고 있어야 한다.
예를 들어 $28$과 $108$의 최대공약수는,
$$
2^2 \cdot 3 = 12
$$
이므로 $A$와의 최대공약수가 $12$인 $C$는 소인수로 $2$를 $2$개 이상, $3$을 $1$개 이상 가지고 있어야 한다.
이때 최대공약수는 공통인 소인수만을 취하므로 다른 수들은 있어도 되고 없어도 된다.
즉, $GCD(A, B) = GCD(A, C)$를 통해 $C$로 가능한 수의 하한을 설정할 수 있다.
$LCM(A, B) = LCM(A, C)$#
위의 내용을 바탕으로 $LCM(A, B)$를 구해보자.
$A$와 $B$를 아래와 같이 소인수분해할 수 있다고 할 때, $$ A = p_{1}^{i_1} \cdot p_{2}^{i_2} \cdot p_{3}^{i_3} \cdot … \newline B = p_{1}^{j_1} \cdot p_{2}^{j_2} \cdot p_{3}^{j_3} \cdot … $$ 두 수의 최소공배수는, $$ LCM(A, B) = p_{1}^{max(i_1, j_1)} \cdot p_{2}^{max(i_1, j_2)} \cdot p_{3}^{max(i_3, j_3)} \cdot … $$ 로 구할 수 있다.
같은 방법으로 $A$와 $C$를 아래와 같이 소인수분해할 수 있다고 할 때, $$ A = p_{1}^{i_1} \cdot p_{2}^{i_2} \cdot p_{3}^{i_3} \cdot … \newline C = p_{1}^{j_1} \cdot p_{2}^{j_2} \cdot p_{3}^{j_3} \cdot … $$ 두 수의 최소공배수는, $$ LCM(A, C) = p_{1}^{max(i_1, j_1)} \cdot p_{2}^{max(i_1, j_2)} \cdot p_{3}^{max(i_3, j_3)} \cdot … $$ 로 구할 수 있다.
그런데 이때 두 최소공배수가 서로 같으려면 $A$와 $C$를 소인수분해할 때 채택된 소인수의 지수 $max(i_k, j_k)$가 $A$와 $B$를 소인수분해할 때 채택된 소인수의 지수와 동일해야 한다.
즉, $LCM(A, B)$의 소인수 $p$에 대해서 그 지수가 $e$라면 $C$는 $p$를 소인수로 $e$개 이하로 가지고 있어야 한다.
예를 들어 $12$과 $108$의 최소공배수는,
$$
2^2 \cdot 3^3 = 108
$$
이므로 $A$와의 최소공배수가 $108$인 $C$는 소인수로 $2$를 $2$개 이하로, $3$을 $3$개 이하로 가져야 한다.
이때 최소공배수는 공통이 아닌 소인수도 모두 취하므로 다른 수들은 없어야 한다.
즉, $LCM(A, B) = LCM(A, C)$를 통해 $C$로 가능한 수의 상한을 설정할 수 있다.
가능한 경우의 수 세기#
위에서 $12$와 $108$의 최대공약수와 최소공배수가 각각, $$ GCD(A, B) = 2^2 \cdot 3 = 12 \newline LCM(A, B) = 2^2 \cdot 3^3 = 108 $$ 임을 알았다.
따라서 이때 $C$로 가능한 수의 하한은 $12$가 되고 상한은 $108$이 된다.
그런데 $C$는 소인수로 $A$와 $B$의 최소공배수가 갖는 소인수만을 가질 수 있으므로, $$ C = 2^{i_1} \cdot 3^{i_2} $$ 로 나타낼 수 있다.
한편 어떤 소인수에 대해 그 소인수는 적어도 최대공약수가 그 소인수를 갖는 개수보다 같거나 많아야 하며,
최소공배수가 그 소인수를 갖는 개수보다 같거나 적어야 한다.
위의 예시에서 $C$는,
$$
2 \le i_1 \le 2 \newline
1 \le i_2 \le 3
$$
이 되어야 하며 그에 따라 가능한 $C$의 개수는,
$$
1 \cdot 3 = 3
$$
이 된다.
한편, 위의 내용은 최대공약수와 최소공배수를 소인수분해했을 때 나오는 어떤 소인수의 지수에 대해, $$ j_k - i_k + 1 $$ 의 곱을 구하는 것이므로, $$ 2^2 \cdot 3 = 12 \newline 2^2 \cdot 3^3 = 108 $$ 사이에 존재하는 수를 구하는 것은, $$ 2^{2 - 2} \cdot 3^{3 - 1} \newline = 2^0 \cdot 3^2 \newline = 3^2 $$ 에서, $$ \frac{LCM(A, B)}{GCD(A, B)} $$ 의 약수의 개수를 구하는 것과 동일하다.
정리#
위에서 $A$, $B$, $C$에 대해, $$ GCD(A, B) = GCD(A, C) \newline LCM(A, B) = LCM(A, C) $$ 이려면 아래와 같은 조건을 만족해야 함을 보았다.
$GCD(A, B)$의 소인수 $p$에 대해서 그 지수가 $e$라면 $C$는 $p$를 소인수로 $e$개 이상으로 가지고 있어야 한다.
$LCM(A, B)$의 소인수 $p$에 대해서 그 지수가 $e$라면 $C$는 $p$를 소인수로 $e$개 이하로 가지고 있어야 한다.
즉, $A$는 $B$를 나누어 떨어지게 할 수 있어야 한다.
이렇게 되면 $GCD(A, B) = A$가 되고 $LCM(A, B) = B$가 되므로 가능한 $C$의 개수를 구하는 것은, $$ \frac{LCM(A, B)}{GCD(A, B)} $$ 이고 이는 다시, $$ B / A $$ 의 약수의 개수를 구하는 것이 된다.
$A$로 $B$를 나누어 떨어지게 할 수 없는 경우는 위의 조건을 만족하지 않으므로 이때 $C$로 가능한 수의 개수는 0이 된다.
구현#
#include <stdio.h>
int main(void) {
int a = 0;
int b = 0;
scanf("%d %d", &a, &b);
if (b % a != 0) {
printf("0\n");
return 0;
}
int temp = b / a;
size_t answer = 0;
for (int i = 1; i * i <= temp; i++) {
if (temp % i == 0) {
answer += i * i == temp ? 1 : 2;
}
}
printf("%zu\n", answer);
return 0;
}
a와 b를 입력 받아 a가 b를 나누어 떨어지게 할 수 없으면 0을 출력한다.
나누어 떨어지게 할 수 있으면 b / a의 약수의 개수를 구해 출력한다.
이때 수의 크기가 커질 수 있으므로 sqrt(temp)까지만 탐색하도록 한다.