문제 백준 2904번 풀이 $A$를 나눌 수 있는 $X$는 $A$의 소인수를 의미합니다. 이 점을 유의해서 문제를 접근해봅시다. 연산을 잘 실행해준 뒤 각 수들의 최대공약수를 최대화하려면, 모든 수들의 소인수를 골고루 분배해주면 됩니다. 예를 들면, $2^5 \cdot 3^1$과 $2^1 \cdot 3^3 $라는 두 수가 있다고 생각해봅시다. 소인수 2는 총 6개, 3은 4개가 있습니다. 이제 위 소인수들을 골고루 분배하면, 각각의 수는 $2^3 \cdot 3^2$이 됩니다. 위 방법(모든 수의 소인수 개수를 세는 것)으로 최대공약수를 최대화할 수 있는데, 몇 번을 움직여야 하는지도 구해야합니다. 예를 들어서, $2^5 \cdot 3^1 \cdot 5^3$이라는 수가 있고, 위에서 구한 최대공약수가 $2..

문제 백준 14256번 풀이 $ SSR(A, B) = (\sqrt{A} + \sqrt{B}) ^ 2 $이 정수가 되어야 합니다. 식 정리를 해봅시다. $$ = A + B + 2 \cdot \sqrt{AB} $$ $A, B$는 이미 정수이므로, $ \sqrt{AB} $가 정수가 되면 됩니다. 따라서, $ AB $가 제곱수가 되면 됩니다. 이제, $ AB $가 제곱수가 되는 경우의 수를 모두 구하면 됩니다. $ A $를 고정시키고, 가능한 $ B $의 개수를 세봅시다. $ A $를 소인수 분해한 뒤, 지수가 홀수인 밑만 곱해준 수를 $ c $라고 정의합니다. 그러면, $ B $는 $ c \cdot k ^ 2 $이라고 둘 수 있습니다. ($k$는 임의의 정수) (왜냐하면, $B$가 항상 $c$의 배수여야 $ ..

문제 백준 1407번 풀이 구간 $[A, B]$를 1씩 증가 시켜보면서 확인하는 방법이 가장 확실하지만, 수의 제한이 무려 $10^{15}$이니 더 빠른 방법을 찾아야 합니다. 우리가 관심 있는 것은 구간 $[A, B]$에서 $2^k$의 배수의 개수입니다. 어떤 수, $k$가 주어졌을 때, 구간 $[A,B]$ 내에서 $k$의 배수의 개수는 $B/k-(A-1)/k$라는 수식을 통해 $O(1)$로 구할 수 있습니다. (단, $A \leq B$) 두번째, $2^{k+1}$의 배수는 모두 $2^k$의 배수입니다. 예를 들면, $32(2^5)$과 같은 수는 $16(2^4)$의 배수임에 동시에 $8, 4, 2, 1$의 배수이기도 합니다. 즉, $2^k$의 배수는 모두 $2^i (i=0,1,...,k)$의 배수라고 ..

문제 BOJ 1484 풀이 문제에서 주어진 조건대로 식을 세워봅시다. 성원이가 기억하고 있는 몸무게를 $ M $, 현재 몸무게를 $ x $로 둡시다. $$ x^2 - M^2 = G $$ $$ (x - M)(x + M) = G $$ $ a = x - M, b = x + M $이라고 둡시다. (단, $ a $, $b $는 정수) $ a \cdot b $이 $ G $가 되려면, $ a $와 $ b $가 $ G $의 약수가 되면 됩니다. $ a $와 $ b $를 알고 있으니 연립 일차 방정식을 사용하여 $ x $를 구할 수 있습니다. $$ x = \frac{a + b}{2} $$ 자연수라는 조건을 충족하려면, $ a + b $가 짝수가 되면 됩니다. 엣지 케이스를 생각해봅시다. 약수 $ a $와 $ b $가 같..